Easiest java dp algorithm (beat 100%)
The idea is from digitDP.\n\nThe KMP is implemented using deterministic finite automaton(Time complexity will be O(26*n), but it is much easier to understand).\
The idea is from [digitDP](https://codeforces.com/blog/entry/53960/).\n\nThe KMP is implemented using deterministic finite automaton(Time complexity will be O(26*n), but it is much easier to understand).\n\nthe range from c1 to c2 = 0 ~ c2 - (0 ~ c1 -1);\n\nDP[pos][k][f] = Number of valid sequences <= char[] c\n/// pos = current position from left side (zero based)\n/// k = number of characters matched with evil string (using dfa to calculate which could be done in O(1) time complexity)\n/// f = the sequence we are building has already become smaller than c? [0 = no, 1 = yes]\n\nTime Complexity: O(n * len(evil))\nSpace Complexity: O(n * len(evil))\n```\nclass Solution {\n    int mod = (int)(1e9+7);\n    long[][][] dp;\n    int n, el;\n    char[] ev;\n    int[][] dfa;\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        if (s1.startsWith(evil) && s2.startsWith(evil)) return 0;\n        this.dfa = KMP(evil);\n        this.n = n;\n        char[] c1 = s1.toCharArray();\n        char[] c2 = s2.toCharArray();\n        c1[c1.length - 1]--;\n        ev = evil.toCharArray();\n        this.el = evil.length();\n        return (int) (((solve(c2) - solve(c1)) % mod) + mod) % mod;\n    }\n\n    int[][] KMP(String pat) {\n        int m = pat.length(), r = 26;\n        int[][] dfa = new int[r][m];\n        dfa[pat.charAt(0) - \'a\'][0] = 1;\n        for (int x = 0, j = 1; j < m; j++) {\n            for (int c = 0; c < r; c++) {\n                dfa[c][j] = dfa[c][x];\n            }\n            dfa[pat.charAt(j)- \'a\'][j] = j + 1;\n            x = dfa[pat.charAt(j)- \'a\'][x];\n        }\n        return dfa;\n    }\n\n    long solve(char[] c) {\n        dp = new long[n][el][2];\n        long res = call(c, 0, 0, 0);\n        return res;\n    }\n\n    long call(char[] c, int pos, int k, int f) {\n        if (pos == n) return 1;\n        if (dp[pos][k][f] != 0) return dp[pos][k][f];\n        long res = 0;\n        int lmt = f == 0 ? c[pos] - \'a\' : 25;\n        for (int nextc = 0; nextc <= lmt; nextc++) {\n            int nk = dfa[nextc][k];\n            if (nk < el) {\n                res += call(c, pos + 1, nk, (f == 0 && nextc == lmt) ? 0 : 1) % mod;\n            }\n        }\n        return dp[pos][k][f] = res;\n    }\n}\n```
[]