[Python] O(nk) KMP with DP, very detailed explanation.
Part 1: Prefix function\nRemind the definition of prefix function on a simple example: let s = ababcaba, then prefix funtion is [0,0,1,2,0,1,2,3], because for e
## Part 1: Prefix function\nRemind the definition of prefix function on a simple example: let `s = ababcaba`, then prefix funtion is `[0,0,1,2,0,1,2,3]`, because for example for substring `ababcab`, the longest equal prefix and suffix `ab` have length 2. There is efficient way to evaluate prefix function, using KMP algorighm. More precisely our function `prefix(self, s)` will give us the length of longest common prefix and suffix, for example for our `s = ababcaba` result will be equal to 3 and we can find it in O(len(s)).\n\n## Part 2: Preprosess evil\nNow, we want to preprocess our `evil` string and create some useful data, we are going ot use later. Let us againg consider `A = evil = ababcaba`. Create `connections` as `T by k` matrix, where `T` is the size of our alphabet and `k = len(evil)`. In `connections[i][j]` we are going to store the length of maximum suffix of string `A_0,...,A_{i-1} + char(j)` which is at the same time is prefix of `A` (here char(0) = "a", char(1) = "b" and so on). A bit difficult to understand, let us consider example: `connections[3][0] = 1`, because `A_0 A_1 A_2 + char(0) = abaa` and this string has suffix `a` which is prefix of `A`. `connections[3][1] = 4`, because  `A_0 A_1 A_2 + char(1) = abab`, which is prefix of `A`.\nLet us fully fill this table `connections`:\n\n|                              | a | b | c | d | e | f |\n|------------------------------|---|---|---|---|---|---|\n| k = 0, starts with ""        | 1 | 0 | 0 | 0 | 0 | 0 |\n| k = 1, starts with "a"       | 1 | 2 | 0 | 0 | 0 | 0 |\n| k = 2, starts with "ab"      | 3 | 0 | 0 | 0 | 0 | 0 |\n| k = 3, starts with "aba"     | 1 | 4 | 0 | 0 | 0 | 0 |\n| k = 4, starts with "abab"    | 3 | 0 | 5 | 0 | 0 | 0 |\n| k = 5, starts with "ababc"   | 6 | 0 | 0 | 0 | 0 | 0 |\n| k = 6, starts with "ababca"  | 1 | 7 | 0 | 0 | 0 | 0 |\n| k = 7, starts with "ababcab" | 8 | 0 | 0 | 0 | 0 | 0 |\n\nLet us note one thing: there is **a lot** of zeros in this table, we can say that this table is sparse. So, we can write this table in different way, I called this list `conn`:\n\n1. `conn[0] = [0,1]`\n2. `conn[1] = [0,1], [1,2]`\n3. `conn[2] = [0,3]`\n3. `conn[3] = [0,1], [1,4]`\n3. `conn[4] = [0,3], [2,5]`\n3. `conn[5] = [0,6]`\n3. `conn[6] = [0,1], [1,7]`\n3. `conn[7] = [0,8]`\n\nLooks better, is it? Howerer we still need one more table: `connections_num_zeros`, where we keep for every `k` and `j` number of zero elements in `k`-th row of matrix `connections`, which we met before element number `j`. Why we need this in the future? Because we need to deal with alphabetical order. \n\n## Part 3: Dynamic progaramming\nLet us reformulate a bit our original problem and introduce funcion `findLesserGood(self, n, k, string, N, evil)`, where `n` is length of or `string`, `k` is length of `evil` and `N` is modulo which we use for long arithmetics. This function finds number of strings alphabetically less or equal than `string`, such that it do not have `evil` substring inside. Then it is enough to apply this function twice (for `s1`, `s2`), get difference and handle border case (string `s1`). \n\nWe have `dp_bord[i][j]` and `dp_notb[i][j]` two  `n x k` arrays, first one to handle border cases, where we search for number of strings, starting with `i` characters of `string` and such that its longest suffix equal to prefix of `evil` has length `j`. Border cases means that next element we can take should be more or equal than corresponding element is `string`.  Second array `dp_notb[i][j]` is for not border cases with the same logic it is number of all string of length `i`, such that the longest common suffix of it and prefix of `evil` has lengh `j`.\n\nPrecalcualted matrices help us efficiently update our tables: when we try to add new symbol we need to understand in `O(1)`, how changes its longes common suffix and prefix of string `evil`. That is why we evaluated our `connections` and `con` tables.\n\n## Part 4: Complexity\n`n` is lenth of original string `s1` and `s2`, `k` is length of `evil` and `T` is the size of alphabet.\n\nTo create connections in part 2 we have complexity `O(k^2T)` (I think it can be improved to `O(kT)` if we do it in smarter way, but it is not the bottleneck, so we keep it like this), because we iterate over k, over all alphabet and apply our `O(k)` complexity prefix function once inside, same time is needed to evaluate `connections_num_zeros`. Memory here is `O(Tk)` to keep couple of matrixes.\n\nComplexity of `findLesserGood` is `O(nkT)`: there is two loops with size `n` and `k` and also inside we go over all `conn` list, which is sure not more than `k`. In fact, this complexity is equal to `O(nk)`, because matrix `connections` is very sparse and `conn` has `O(k)` elements instead of `O(kT)` (if I am wrong, please let me know!). Space complexity is obviously `O(nk)`.\n\nFinally, time complexity is `O(nk + k^2T) = O(nk)` for our constraints and space complexity is `O(Tk + nk) = O(nk)` also.\n\n## Part 5. Code\nNow, if we put all the stuff we discussed togeter, we can have the following code:\n\n```\nclass Solution:\n    def prefix(self, s):\n        p = [0] * len(s)\n        for i in range(1, len(s)):\n            k = p[i - 1]\n            while k > 0 and s[k] != s[i]: \n                k = p[k - 1]\n            if s[k] == s[i]:\n                k += 1\n            p[i] = k\n        return p[-1]\n\n    def CreateConnections(self, evil, T):\n        k = len(evil)\n        connections = [[-1]*T for _ in range(k)]\n        conn = [[] for _ in range(k)]\n        for i in range(k):\n            for letter in self.alphabet:\n                curr_max = self.prefix(evil + "#" + evil[0:i] + letter)\n               \n                if curr_max != k:    #process case when we reached the end of evil string\n                    connections[i][ord(letter) - ord("a")] = curr_max\n\n                    if curr_max != 0:\n                        conn[i].append([ord(letter) - ord("a"), curr_max])\n\n        connections_num_zeros = [[0] for _ in range(k)]\n        for i in range(k):\n            for j in range(1, T + 1):\n                connections_num_zeros[i] += [connections_num_zeros[i][-1] + (connections[i][j-1] == 0)]\n\n        return connections_num_zeros, conn\n\n    def findLesserGood(self, n, k, string, N, evil):\n        dp_bord = [[0]*k for _ in range(n)]\n        dp_notb = [[0]*k for _ in range(n)]\n          \n        dp_bord[0][0] = 1\n                  \n        for it_n in range(n-1):\n            for it_k in range(k):\n                ord_num = ord(string[it_n + 1]) - ord("a")\n\n                for letter, s  in self.con[it_k]:\n                    dp_notb[it_n+1][s] += dp_notb[it_n][it_k]\n                    if letter < ord_num:\n                        dp_notb[it_n+1][s] += dp_bord[it_n][it_k]\n\n                dp_notb[it_n +1][0] += self.con_numzero[it_k][-1] * dp_notb[it_n][it_k]     \n                dp_notb[it_n +1][0] += self.con_numzero[it_k][ord_num] * dp_bord[it_n][it_k]\n                        \n                dp_notb[it_n+1][it_k] %= N\n\n            index = self.prefix(evil + "#" + string[0:it_n+2])\n            if index != k and sum(dp_bord[it_n]) != 0:\n                dp_bord[it_n + 1][index] = 1\n   \n        return sum(dp_bord[-1]) + sum(dp_notb[-1])\n\n    def findGoodStrings(self, n, s1, s2, evil):\n        self.alphabet = string.ascii_lowercase\n        N, k = 10**9 + 7, len(evil)\n      \n        self.con_numzero, self.con = self.CreateConnections(evil, len(self.alphabet))\n        res1 = self.findLesserGood(n + 1, k, "#" + s2, N, evil)\n        res2 = self.findLesserGood(n + 1, k, "#" + s1, N, evil)\n        return (res1 - res2 + 1 - (evil in s1)) % N\n```\n\nIf you have any questions, feedback or improvements, feel free to ask. If you reached this place and like the explanations, please **upvote**!
[]