c++ | 89.29% faster than all | digit dp & kmp
```\ntypedef long long   ll;\nconst int           M   = 10 + 5e1;\nconst int           N   = 10 + 5e2;\nconst ll            mod =  7 + 1e9;\n\nint     n, m;\nll
```\ntypedef long long   ll;\nconst int           M   = 10 + 5e1;\nconst int           N   = 10 + 5e2;\nconst ll            mod =  7 + 1e9;\n\nint     n, m;\nll      f[N][M];\nint     g[N][M];\n\nint     Next[N];\nint     dp[N];\nstring  str;\n\n\nclass Solution {\npublic:\n    int findGoodStrings(int nn, string s1, string s2, string evil) {\n        memset(Next, 0, sizeof(Next));\n        memset(dp, 0, sizeof(dp));\n        memset(f, 0, sizeof(f));\n        memset(g, 0, sizeof(g));\n        n = s1.size();\n        m = evil.size();\n        s1 = "#"+s1, s2 = "#"+s2, evil = "#"+evil;\n        \n        \n        // dp1\uFF1A kmp\n        prefix(evil);\n        \n        // dp2\n        for (int i = 0; i < m; i++) {\n            for (int ch = \'a\'; ch <= \'z\'; ch++) g[i][ch-\'a\'] = kmp(evil, i, ch);\n        }\n        \n        // dp3\n        for (int t = 0; t <  m; t++) f[0][t] = 1;\n        for (int i = 1; i <= n; i++) {\n            for (int t = 0; t < m; t++) {                                f[i][t] = f[i-1][t+1];\n                for (int ch = \'a\'; ch <= \'z\'; ch++) if (ch != evil[t+1]) f[i][t] = (f[i][t] + f[i-1][ g[t][ch-\'a\'] ]) % mod;\n            }\n        }\n        \n        \n        // Digit dp\n        str = s1;       ll l = dfs(1, 0, true);\n        str = s2;       ll r = dfs(1, 0, true);\n        return (r-l+(1-isEvil(s1,evil))+mod)%mod;    \n    }\n    \n    \n    ll  dfs(int k, int len, bool limit) {\n        if (k >  n) return 1;\n        if (!limit) return f[n-k+1][len];\n        \n        ll  ans = 0, beg = \'a\', upp = limit?str[k]:\'z\';\n        for (int ch = beg; ch <= upp; ch++) {                                            \n            if (g[len][ch-\'a\'] != m) ans = (ans + dfs(k+1, g[len][ch-\'a\'], limit&&ch==str[k])) % mod;\n        }\n        return ans;\n    }\n    \n    \n    void prefix(string& s) {\n        for (int i = 2, k = 0; i <= m; i++) {\n            while (k > 0 && s[k+1] != s[i]) k = Next[k];\n            if (s[k+1] == s[i]) k++;\n            Next[i] = k;\n        }\n    }\n    \n    int kmp(string& s, int k, char ch) {\n        while (k > 0 && s[k+1] != ch) k = Next[k];\n        if (s[k+1] == ch) k++;\n        return k;\n    }\n    \n    bool isEvil(string& s, string& p) {\n        for (int i = 1, k = 0; i <= n; i++) {\n            while (k > 0 && (k == m || p[k+1] != s[i])) k = Next[k];\n            if (p[k+1] == s[i]) k++;\n            if (m == (dp[i]=k)) return true;\n        }\n        return false;\n    }\n};\n
[]