Find All Good Strings: นับสตริงที่ดีใน C++

ปัญหา

กำหนด s1, s2 (ความยาว n) และสตริง evil หาจำนวนสตริง good ที่:

1. ความยาว = n
2. s1 ≤ good ≤ s2 (Lexicographically)
3. ไม่มี evil เป็น Substring

คำตอบ modulo 10^9 + 7

ตัวอย่าง: n=2, s1="bb", s2="db", evil="a" → 51 วิธี

แนวคิด: DP + KMP Automaton (Aho-Corasick สำหรับ Pattern เดียว)

State

dp[pos][matched_len][tight] = จำนวนวิธีสร้าง prefix ยาว pos ที่: - matched_len = ความยาวของ suffix ที่ match กับ prefix ของ evil (0..|evil|-1) - tight = 0/1 ว่า prefix นี้เท่ากับ prefix ของ s2 (upper bound) หรือไม่

ใช้ KMP Failure Function (Prefix Function) คำนวณ trans[state][char] = state ใหม่หลังเพิ่ม char

การนับในช่วง [s1, s2]

count(s2) - count(s1-1) โดย s1-1 คือสตริงก่อน s1 ทาง Lexicographic

โค้ด C++ (Simple Version)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
    vector<int> computeLPS(string pat) {
        int m = pat.size();
        vector<int> lps(m, 0);
        for (int i = 1, len = 0; i < m; ) {
            if (pat[i] == pat[len]) lps[i++] = ++len;
            else if (len) len = lps[len-1];
            else lps[i++] = 0;
        }
        return lps;
    }
    
    vector<array<int, 26>> buildTrans(string evil) {
        int m = evil.size();
        vector<int> lps = computeLPS(evil);
        vector<array<int, 26>> trans(m);
        for (int state = 0; state < m; state++) {
            for (int c = 0; c < 26; c++) {
                char ch = 'a' + c;
                int ns = state;
                while (ns > 0 && evil[ns] != ch) ns = lps[ns-1];
                if (evil[ns] == ch) ns++;
                trans[state][c] = ns;
            }
        }
        return trans;
    }
    
    ll solve(string s, string evil, auto& trans, auto& dp, int pos, int state, bool tight) {
        if (state == evil.size()) return 0;  // พบ evil
        if (pos == s.size()) return 1;
        
        ll& res = dp[pos][state][tight];
        if (res != -1) return res;
        res = 0;
        
        char limit = tight ? s[pos] : 'z';
        for (char c = 'a'; c <= limit; c++) {
            int ns = trans[state][c - 'a'];
            bool ntight = tight && (c == limit);
            res = (res + solve(s, evil, trans, dp, pos+1, ns, ntight)) % MOD;
        }
        return res;
    }
    
    string prevString(string s) {  // s - 1
        for (int i = s.size()-1; i >= 0; i--) {
            if (s[i] > 'a') { s[i]--; break; }
            s[i] = 'z';
        }
        return s;
    }
    
public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        auto trans = buildTrans(evil);
        int m = evil.size();
        
        // Count for s2
        vector dp1(n+1, vector(m, vector<ll>(2, -1)));
        ll right = solve(s2, evil, trans, dp1, 0, 0, true);
        
        // Count for s1-1
        string s1_prev = prevString(s1);
        vector dp2(n+1, vector(m, vector<ll>(2, -1)));
        ll left = solve(s1_prev, evil, trans, dp2, 0, 0, true);
        
        return (right - left + MOD) % MOD;
    }
};

int main() {
    Solution ob;
    cout << ob.findGoodStrings(2, "bb", "db", "a");  // 51
    return 0;
}

ความซับซ้อน

• Time: O(n × |evil| × 26)
• Space: O(n × |evil| × 2)

Input / Output

Input:  n=2, s1="bb", s2="db", evil="a"
Output: 51