DP without KMP Python
state parameter (curr_index, prev_string, evil_index)\nif prev_string was smaller than s2 and larger than s1 u can use any ch for curr_index\nelse u gonna have 
state parameter (curr_index, prev_string, evil_index)\nif prev_string was smaller than s2 and larger than s1 u can use any ch for curr_index\nelse u gonna have to use a s1[c_i] <= ch <= s2[c_i]\nalso make sure that if ch == evil[e_i], u incremenet e_i += 1, but make sure it never reaches end\n\nImportant question is what happens if ch != evil[e_i]? do you just make it 0?\nno because for eg if evil = baabbaaba and curr_string = baabbaabb, u can see that baaabb is present in both start of evil and end of curr_string so next e_i would be 5.\n\nThis is where KMP comes in. If you didnt use KMP and did brute force your solution would take around 4000ms - 9000ms (acceptable time)\nWith KMP it takes arounf 600 - 700ms\n\n**WITHOUT KMP**\n```\ndef findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n    chars = string.ascii_lowercase\n    m = len(evil)\n    @lru_cache(None)\n    def dp(c_i, prev_larger, prev_smaller, c_evil):\n        if c_i == n:\n            return 1\n        \n        e_i = len(c_evil)\n        ways = 0\n        for ch in chars:\n            if not prev_larger and ch < s1[c_i]: continue\n            if not prev_smaller and ch > s2[c_i]: continue\n            if e_i == m-1 and ch == evil[e_i]: continue\n\n            next_evil = c_evil + ch\n            if evil[e_i] != ch:\n                r = len(next_evil); l = 0\n                while evil[:r] != next_evil[l:] and r:\n                    l += 1; r -= 1\n                next_evil = evil[:r]\n            ways += dp(c_i + 1, prev_larger|(ch>s1[c_i]), prev_smaller|(ch<s2[c_i]), next_evil)\n            \n        return ways%1000000007\n    \n    return dp(0, 0, 0, "")\n```\n\n**WITH KMP**\n```\ndef findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n    chars = string.ascii_lowercase\n\n    m = len(evil)\n    lps = [0]*m\n    j = 0\n    for i in range(1, m):\n        while j and evil[j]!=evil[i]:\n            j = lps[j-1]\n        if evil[j] == evil[i]:\n            j += 1\n        lps[i] = j\n\n    @lru_cache(None)\n    def dp(c_i, prev_larger, prev_smaller, e_i):\n        if c_i == n:\n            return 1\n\n        ways = 0\n\n        for ch in chars:\n            if not prev_larger and ch < s1[c_i]: continue\n            if not prev_smaller and ch > s2[c_i]: continue\n            if e_i == m-1 and ch == evil[e_i]: continue\n            \n            if ch == evil[e_i]:\n                j = e_i + 1\n            else:\n                j = e_i\n                while j and evil[j] != ch:\n                    j = lps[j-1]\n                if evil[j] == ch:\n                    j += 1\n\n            ways += dp(c_i + 1, prev_larger|(ch>s1[c_i]), prev_smaller|(ch<s2[c_i]), j)\n        return ways%1000000007\n\n        return dp(0, 0, 0, 0)\n```
['Dynamic Programming', 'String Matching', 'Python']