这题是典型的：

字符串数位 DP + KMP

两部分限制分别是：

• s1 <= 当前字符串 <= s2：用数位 DP 的上下界状态；
• 不能包含 evil：用 KMP 记录当前已经匹配了 evil 的多少位。

DP 状态

定义：

dfs(pos, match, lowLimit, highLimit)

表示：

• pos：正在填写第几个字符；
• match：当前字符串后缀与 evil 前缀匹配的长度；
• lowLimit：前面是否一直贴着下界 s1；
• highLimit：前面是否一直贴着上界 s2。

例如：

evil = "abab"
match = 3

表示当前字符串的后缀是：

"aba"

如果 match == evil.size()，说明已经出现了完整的 evil，该方案不能继续。

字符选择范围

当前处于位置 pos：

char left = lowLimit ? s1[pos] : 'a';
char right = highLimit ? s2[pos] : 'z';

然后枚举：

for (char c = left; c <= right; ++c)

新的边界状态：

newLowLimit = lowLimit && (c == s1[pos]);
newHighLimit = highLimit && (c == s2[pos]);

KMP 的作用

如果直接在每次加入字符后重新检查是否出现 evil，复杂度会比较高。

KMP 可以根据：

当前匹配长度 match
新加入字符 c

快速得到新的匹配长度：

nextMatch[match][c]

我们提前把所有转移算出来，DP 时就能 O(1) 转移。

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    static constexpr int MOD = 1000000007;

    int n, m;
    string lowerBound, upperBound, evil;

    vector<int> prefix;
    int nextMatch[51][26];

    // memo[pos][match][lowLimit][highLimit]
    int memo[501][51][2][2];

    int dfs(
        int pos,
        int match,
        bool lowLimit,
        bool highLimit
    ) {
        if (pos == n) {
            return 1;
        }

        int& result = memo[pos][match][lowLimit][highLimit];

        if (result != -1) {
            return result;
        }

        result = 0;

        char left = lowLimit ? lowerBound[pos] : 'a';
        char right = highLimit ? upperBound[pos] : 'z';

        for (char c = left; c <= right; ++c) {
            int newMatch = nextMatch[match][c - 'a'];

            // 已经出现完整的 evil
            if (newMatch == m) {
                continue;
            }

            bool newLowLimit =
                lowLimit && (c == lowerBound[pos]);

            bool newHighLimit =
                highLimit && (c == upperBound[pos]);

            result += dfs(
                pos + 1,
                newMatch,
                newLowLimit,
                newHighLimit
            );

            if (result >= MOD) {
                result -= MOD;
            }
        }

        return result;
    }

    void buildKMP() {
        prefix.assign(m, 0);

        // 构造 evil 的前缀函数
        for (int i = 1; i < m; ++i) {
            int j = prefix[i - 1];

            while (j > 0 && evil[i] != evil[j]) {
                j = prefix[j - 1];
            }

            if (evil[i] == evil[j]) {
                ++j;
            }

            prefix[i] = j;
        }

        // 预处理：当前匹配 state，再加入字符 c 后的新状态
        for (int state = 0; state < m; ++state) {
            for (int c = 0; c < 26; ++c) {
                char ch = 'a' + c;
                int j = state;

                while (j > 0 && evil[j] != ch) {
                    j = prefix[j - 1];
                }

                if (evil[j] == ch) {
                    ++j;
                }

                nextMatch[state][c] = j;
            }
        }
    }

public:
    int findGoodStrings(
        int n_,
        string s1,
        string s2,
        string evil_
    ) {
        n = n_;
        lowerBound = s1;
        upperBound = s2;
        evil = evil_;
        m = evil.size();

        buildKMP();
        memset(memo, -1, sizeof(memo));

        return dfs(0, 0, true, true);
    }
};

状态转移过程

假设：

s1 = "aa"
s2 = "da"
evil = "b"

初始状态：

dfs(0, 0, true, true)

第一个位置允许选择：

'a' 到 'd'

如果选择 'a'：

lowLimit 仍然为 true
highLimit 变成 false

下一位范围是：

'a' 到 'z'

如果选择 'c'：

lowLimit = false
highLimit = false

下一位也可以任意选择：

'a' 到 'z'

如果选择 'd'：

lowLimit = false
highLimit = true

下一位最多只能选择：

'a'

与此同时，每加入一个字符，就通过 KMP 检查是否形成了 evil。

复杂度

DP 状态数：

n × |evil| × 2 × 2

每个状态枚举 26 个字符，因此：

时间复杂度：O(n × |evil| × 26)
空间复杂度：O(n × |evil|)

这题最关键的状态设计是：

位置 + evil 匹配长度 + 是否贴着下界 + 是否贴着上界

其中数位 DP 负责字典序范围，KMP 状态机负责禁止出现 evil。

至于KMP：

KMP 可以先记住一句话：

用已经匹配过的信息，避免失配后从头开始比较。

它主要解决：

在文本串 text 中查找模式串 pattern

例如：

text    = "ababababca"
pattern = "ababca"

暴力匹配在失配后会回退，KMP 则利用模式串自身的重复结构快速跳转。

一、KMP 中的两个字符串

设：

text    // 主串
pattern // 模式串

例如：

text    =    a b a b a b c
pattern =    a b a b c

KMP 预处理的是 pattern，而不是 text。

二、前缀和后缀

对于字符串：

"abab"

它的前缀有：

"a"
"ab"
"aba"

后缀有：

"b"
"ab"
"bab"

最长相等的前缀和后缀是：

"ab"

长度为 2。

定义：

pi[i]

表示：

pattern[0..i] 中，最长相等前缀和后缀的长度。

例如：

pattern = "ababaca"

对应：

下标：  0 1 2 3 4 5 6
字符：  a b a b a c a
pi：    0 0 1 2 3 0 1

解释 pi[4]：

"ababa"

最长相等前后缀为：

"aba"

长度为 3。

三、如何计算前缀函数

vector<int> prefixFunction(string pattern) {
    int m = pattern.size();
    vector<int> pi(m);

    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];

        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            ++j;
        }

        pi[i] = j;
    }

    return pi;
}

最关键的是：

j = pi[j - 1];

当出现失配时，不是让 j 直接变成 0，而是跳到当前匹配串的最长相等前后缀长度。

例如：

pattern = "abab"
当前已经匹配了 "aba"
接下来失配

已经匹配的 "aba" 的最长相等前后缀是 "a"，所以跳到长度 1，而不是从 0 重新开始。

四、普通 KMP 查找模板

int kmp(string text, string pattern) {
    vector<int> pi = prefixFunction(pattern);

    int n = text.size();
    int m = pattern.size();

    int j = 0;

    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }

        if (text[i] == pattern[j]) {
            ++j;
        }

        if (j == m) {
            // pattern 在 text 中出现
            return i - m + 1;
        }
    }

    return -1;
}

j 表示：

当前 text 后缀与 pattern 前缀匹配的长度

当：

j == m

说明模式串完整匹配。

五、为什么你的题目也要用 KMP

你的题目不是单纯查找一次 evil，而是在 DP 中不断构造字符串。

假设：

evil = "abab"

当前已经构造出的字符串后缀是：

"aba"

这说明当前：

match = 3

如果下一个字符继续加入：

'b'

就得到：

match = 4

说明已经出现完整的 evil，这个方案要丢弃。

如果下一个字符是：

'c'

发生失配，不能简单把 match 变成 0。因为 "aba" 的后缀 "a" 仍然可能是 evil 的前缀。

KMP 会自动跳转：

"aba" -> "a"

于是新的匹配长度是 1。

这就是题目 DP 中的：

nextMatch[match][c]

它表示：

当前已经匹配 match 个字符，再加入字符 c 后，新的匹配长度是多少。

六、如何构造 nextMatch

for (int state = 0; state < m; ++state) {
    for (char c = 'a'; c <= 'z'; ++c) {
        int j = state;

        while (j > 0 && evil[j] != c) {
            j = pi[j - 1];
        }

        if (evil[j] == c) {
            ++j;
        }

        nextMatch[state][c - 'a'] = j;
    }
}

举例：

evil = "abab"
当前 match = 3
当前匹配：aba
加入字符：b

计算过程：

evil[3] == 'b'
j 从 3 变成 4

得到：

nextMatch[3]['b'] = 4

因为 4 == evil.size()，说明出现了完整的 evil。

七、需要注意的边界问题

在这段代码中：

if (evil[j] == c) {
    ++j;
}

必须保证 j < m。

因为如果 j == m，说明已经完整匹配，通常应该直接丢弃这个状态，不再继续访问 evil[j]。

你的 DP 代码中使用的是：

if (newMatch == m) {
    continue;
}

所以 nextMatch 只会从 state = 0 到 m-1 构造，不会传入 state == m，这是正确的。

八、KMP 最应该记住的内容

1. 前缀函数含义

pi[i]

表示：

pattern[0..i] 的最长相等前缀和后缀长度

2. 失配跳转

j = pi[j - 1];

3. 匹配成功

++j;

4. 完整匹配

if (j == pattern.size())

5. 复杂度

构造 pi：O(m)
文本匹配：O(n)

九、和普通 DP 的联系

在你的字符串计数题中，可以把 KMP 看成一个有限状态机：

状态：当前匹配了 evil 的前几位
输入：下一个字符
转移：nextMatch[state][char]

DP 只需要在这个状态机上走：

dp[位置][KMP状态][上下界状态]

因此 KMP 在这里不是单独用来“查找字符串”，而是用来：

记录当前构造字符串的后缀，距离形成 evil 还差多少。