DP on automata state
Consider the 4d state dp(i, b1, b2, k) as the number of strings such that:\n1. has length n\n2. if b1, then it is already large than s1\n3. if b2, then it is al
Consider the 4d state dp(i, b1, b2, k) as the number of strings such that:\n1. has length n\n2. if b1, then it is already large than s1\n3. if b2, then it is already less than s2\n4. It has matched the pattern evil up to k characters.\n\nWe build the state transition on s using KMP. (It can be extended to multiple patterns using AC automata states). What left is a simple DP with consideration for the case when we passed the length of s1 or s2.\n\nSee the implementatio below:\n```\nint record[505][2][2][51];\n\nclass Solution {\npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        int m = evil.size();\n        vector<int> fail(m+1, 0);\n        int s = 0;\n        for (int i = 2; i <= m; i++) {\n            while (s > 0 && evil[i-1] != evil[s]) s = fail[s];\n            if (evil[i-1] == evil[s]) s++;\n            fail[i] = s;\n        }\n        memset(record, 0, sizeof(record));\n        record[0][0][0][0] = 1;\n        for (int i = 1; i <= n; i++) {\n            for (int b1 = 0; b1 <= 1; b1++) {\n                for (int b2 = 0; b2 <= 1; b2++) {\n                    for (int s = 0; s < m; s++) {\n                        if (record[i-1][b1][b2][s] == 0) continue;\n                        char st = b1 ? \'a\' : s1[i-1];\n                        char ed = b2 ? \'z\' : s2[i-1];\n                        for (char c = st; c <= ed; c++) {\n                            int e1 = b1 ? 1 : (i >= s1.length() || c > s1[i-1]);\n                            if (b2 == 0 && i-1 >= s2.length()) continue;\n                            int e2 = b2 ? 1 : c < s2[i-1];\n                            int sp = s;\n                            while (sp > 0 && evil[sp] != c) sp = fail[sp];\n                            if (evil[sp] == c) sp++;\n                            // transition from [i-1][b1][b2][s] --read c-> [i][e1][e2][s\']\n                            if (sp < m) {\n                                record[i][e1][e2][sp] += record[i-1][b1][b2][s];\n                                record[i][e1][e2][sp] %= 1000000007;\n                            }\n                        }\n                    }\n                }\n            }\n        }\n        int result = 0;\n        for (int b1 = 0; b1 <= 1; b1++) {\n            for (int b2 = 0; b2 <= 1; b2++) {\n                for (int s = 0; s < m; s++) {\n                    result += record[n][b1][b2][s];\n                    result %= 1000000007;\n                }\n            }\n        }\n        return result;\n    }\n};
[]