first Digit DP problem
I failed to solve this problem in contest.\nand  i learnt digit dp later, then find it just use the template with a KMP trick.\n\nfirst find the resources to le
I failed to solve this problem in contest.\nand  i learnt digit dp later, then find it just use the template with a KMP trick.\n\nfirst find the resources to learn digit dp\n\nin its template it use a dp array with dp[ ori_digits ] [ evil_digits ] [limit]\nfor example find  numbers between 0 ~ 1,024 without contains 99, means \'99,199,299,399,...991...999\' should not be counted.\nthe origin digits is 4, ->[1,0,2,4];\nthe eveil digits is 2, ->[9,9]\nlimit means previous char is touch the limit. 1,0,2, x  touched the limit. \nwhen touch the limit, we only could forloop ( 0 -> 4)\n1,0,1, x is not, not touch the limit, we could forloop all (0 -> 9)\n\nnow the above questions is just a dfs with memorization\n\ndigit dp template\n```\nint M = 1000000007;\n    long[][][] dp;\n    int[] oriDigits;\n    int[] evilDigits = new int[]{9,9};\n    public int solve(int n) {\n        // init oriDigits\n        char[] cs = ("" + n).toCharArray();\n        oriDigits = new int[cs.length]; // {1.0.2.4}\n        for (int i = 0; i < cs.length; i++) oriDigits[i] = cs[i] - \'0\';\n\n        dp = new long[oriDigits.length][evilDigits.length][2];\n        return (int) (dfs(0,0, true) % M);\n    }\n\n    private long dfs(int oriIdx, int evilIdx, boolean limit) {\n        if (evilIdx == evilDigits.length) return 0;\n        if (oriIdx == oriDigits.length) return 1;\n        if (dp[oriIdx][evilIdx][limit?1:0] > 0) return dp[oriIdx][evilIdx][limit?1:0];\n        int maxDigit = limit ? oriDigits[oriIdx] : 9;\n        long res = 0;\n        for (int i = 0; i <= maxDigit; i++) {\n            int nextEvilIdx = 0;\n            if (i == evilDigits[evilIdx]) nextEvilIdx = evilIdx + 1;\n            else if (i == evilDigits[0]) nextEvilIdx = 1; // because evilDigits only 2 digit, if > 2, we need use kmp to cal\n            res += dfs(oriIdx + 1, nextEvilIdx, limit && i == maxDigit);\n            res %= M;\n        }\n        return dp[oriIdx][evilIdx][limit?1:0] = res;\n    }\n```\n\nso with this template, we only need to solve how about there are another upper bound\n\nit is easy with solve with two lower bound\n\nlike solve(1024~2048) could be solve(2048) - solve(1023)\n\nthen the problem is solved quicky with the template\n\n```\nint M = 1000000007;\n    char[] es; // evil string\n    long[][][] dp;\n    int[] next;\n    public int findGoodStrings(int n, String s1, String s2, String evil) {\n        es = evil.toCharArray();\n\t\t// build kmp next array\n        next = new int[es.length];\n        next[0] = -1;\n        for (int i = 1, j = 0; i < es.length; i++) {\n            next[i] = es[i] == es[j] ? next[j] : j;\n            while (j >= 0 && es[i] != es[j]) j = next[j];\n            j++;\n        }\n        long pre = solve(s1), ans = (solve(s2) - pre + M) % M;\n        if (s1.indexOf(evil) == -1) ans++;\n        return (int) (ans % M);\n    }\n    char[] ds; // ori digit string\n    long solve(String digits) {\n        dp = new long[digits.length()][es.length][2];\n        ds = digits.toCharArray();\n        return dfs(0, 0, true);\n    }\n    long dfs(int idx, int eidx, boolean limit) {\n        if (eidx == es.length) return 0;\n        if (idx == ds.length) return 1;\n        if (dp[idx][eidx][limit?1:0] > 0) return dp[idx][eidx][limit?1:0];\n        int max = limit ? ds[idx] : \'z\';\n        long res = 0;\n        for (int i = \'a\'; i <= max; i++) {\n            int tmp = eidx;\n\t\t\t// use kmp next array to find next evil string idx position\n            while (tmp >= 0 && es[tmp] != i) tmp = next[tmp];\n            res += dfs(idx + 1, tmp + 1, limit && (i == max));\n            res %= M;\n        }\n        return dp[idx][eidx][limit?1:0] = res;\n    }\n```\n
[]