Straightforward Iterative DP with KMP, O(NM) Time O(M) Space, 8ms c++
c++\nconstexpr int mod = 1000000007;\n\n// O(n) KMP\n// len[i] is the longest common prefix and suffix of s[0...i], eg. next[i] in normal KMP algo.\n// nxt[i][c
```c++\nconstexpr int mod = 1000000007;\n\n// O(n) KMP\n// len[i] is the longest common prefix and suffix of s[0...i], eg. next[i] in normal KMP algo.\n// nxt[i][c] here is the next matching position when meeting a character \'c\' at position i, \n// eg. an automaton of only one string. (So this question can have multiple evil strings then\n// the solution is to DP on the state of automaton. )\nint nxt[50][26], len[50];\nvoid get_next(string& s) {\n    int n = s.size();\n    len[0] = 0;\n    int matching = 0;\n    int cur = 1;\n    while (cur < n) {\n        if (s[cur] == s[matching]) {\n            matching += 1;\n            len[cur] = matching;\n            cur += 1;\n        } else if (matching > 0) {\n            matching = len[matching - 1];\n        } else {\n            len[cur] = 0;\n            cur += 1;\n        }\n    }\n    for (int ch = 0; ch < 26; ++ch) nxt[0][ch] = \'a\' + ch == s[0] ? 1 : 0;\n    for (cur = 1; cur < n; ++cur) {\n        for (int ch = 0; ch < 26; ++ch) {\n            if (s[cur] == ch + \'a\') {\n                nxt[cur][ch] = cur + 1;\n            } else {\n                nxt[cur][ch] = nxt[len[cur - 1]][ch];\n            }\n        }\n    }\n}\n\ninline void add(int& ref, int val) {\n    if ((ref += val) >= mod) ref -= mod;\n}\n\n//   len  match  >s1  <s2\nint f[2]  [50]   [2]  [2];\n\nclass Solution {\npublic:\n    int findGoodStrings(int n, string& s1, string& s2, string& evil) {\n        int m = evil.size();\n        get_next(evil);\n        \n        memset(f[0], 0, sizeof(f[0]));\n        f[0][0][0][0] = 1;\n        for (int i = 0; i < n; ++i) {\n            memset(f[i & 1 ^ 1], 0, sizeof(f[i + 1]));\n            for (int matching = 0; matching < m; ++matching) {\n                for (int greater_s1 = 0; greater_s1 < 2; ++greater_s1) {\n                    for (int less_s2 = 0; less_s2 < 2; ++less_s2) {\n                        if (f[i & 1][matching][greater_s1][less_s2] == 0) continue;\n                        for (int ch = 0; ch < 26; ++ch) {\n                            if (!greater_s1 && ch < s1[i] - \'a\') continue;\n                            if (!less_s2 && ch > s2[i] - \'a\') continue;\n                            if (nxt[matching][ch] >= m) continue;\n                            add(f[i  & 1 ^ 1]\n\t\t\t\t\t\t\t     [nxt[matching][ch]]\n\t\t\t\t\t             [greater_s1 || ch > s1[i] - \'a\']\n\t\t\t\t\t\t\t     [less_s2 || ch < s2[i] - \'a\'],\n\t\t\t\t\t\t\t\tf[i & 1][matching][greater_s1][less_s2]);\n                        }\n                    }\n                }\n            }\n        }\n        \n        int res = 0;\n        for (int matching = 0; matching < m; ++matching)\n            for (int i = 0; i < 2; ++i)\n                for (int j = 0; j < 2; ++j)\n                    add(res, f[n & 1][matching][i][j]);\n        return res;\n    }\n};\n```
[]