Find All Good Strings trong C++

Cho độ dài n, chuỗi s1, s2 (|s1|=|s2|=n), và chuỗi evil. Chuỗi tốt: độ dài n, s1 ≤ chuỗi ≤ s2 (theo từ điển), không chứa evil làm substring. Đếm số chuỗi tốt modulo 10^9+7.

Ví dụ: n=2, s1="bb", s2="db", evil="a" → 51 chuỗi tốt.

Giải thuật (DP + KMP Automaton)

Xây automaton KMP cho evil. DP[pos][matched][tight] = số cách xây tiền tố độ dài pos, đã match evil độ dài matched, tight=1 nghĩa là tiền tố bằng s2[0..pos-1]. Chuyển trạng thái qua 26 chữ cái.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int N = 500, M = 50;
const lli MOD = 1e9 + 7;
int dp[N+1][M+1][2];
int trans[M+1][26];

class Solution {
    int add(lli a, lli b) { return (a + b) % MOD; }
    
    lli solve(int n, string s, string evil) {
        reverse(evil.begin(), evil.end());
        memset(trans, 0, sizeof(trans));
        memset(dp, 0, sizeof(dp));
        
        int m = evil.size();
        // Build KMP transition
        for (int i = 0; i < m; i++) {
            string pref = evil.substr(0, i);
            for (int c = 0; c < 26; c++) {
                string ns = pref + char('a' + c);
                for (int k = i + 1; k >= 0; k--) {
                    if (ns.substr(ns.size() - k) == evil.substr(0, k)) {
                        trans[i][c] = k;
                        break;
                    }
                }
            }
        }
        
        dp[n][0][1] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                for (int c = 0; c < 26; c++) {
                    for (int tight : {0, 1}) {
                        int ntight;
                        if (c > s[i] - 'a') ntight = 0;
                        else if (c < s[i] - 'a') ntight = 1;
                        else ntight = tight;
                        int nj = trans[j][c];
                        if (nj == m) continue; // tránh evil
                        dp[i][nj][ntight] = add(dp[i][nj][ntight], dp[i+1][j][tight]);
                    }
                }
            }
        }
        
        lli res = 0;
        for (int i = 0; i < m; i++) res = add(res, dp[0][i][1]);
        return res;
    }
    
public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        // Tính f(s2) - f(s1-1)
        bool allA = true;
        for (char c : s1) if (c != 'a') { allA = false; break; }
        
        int left = 0;
        if (!allA) {
            // s1-- (giảm chuỗi)
            for (int i = n - 1; i >= 0; i--) {
                if (s1[i] != 'a') { s1[i]--; break; }
                s1[i] = 'z';
            }
            left = solve(n, s1, evil);
        }
        int right = solve(n, s2, evil);
        return (right - left + MOD) % MOD;
    }
};

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

Đầu vào / Đầu ra

Input: 2, "bb", "db", "a"
Output: 51