【python3】 A natural DP solution, faster and simpler than the Hint solution, without KMP
For the fast:\nRuntime: 320 ms, faster than 100.00% of Python3 online submissions for Find All Good Strings.\nMemory Usage: 17.8 MB, less than 100.00% of Python
For the fast:\nRuntime: 320 ms, faster than 100.00% of Python3 online submissions for Find All Good Strings.\nMemory Usage: 17.8 MB, less than 100.00% of Python3 online submissions for Find All Good Strings.\n\nFor the idea: \nFirstly, the s1 and s2 looks boring. let\'s solve a sub-problem without them.\ni.e. \n**Given the string evil and size n. Return the number of good strings.** \n**A good string has size n, it does not contain the string evil as a substring. **\n\nMark the solusion of this problem is S(n), then we find S(n) = 26 * S(n-1) - C(n-1, len(evil)-1)\nwhich means all the solusions of n-1 combine with a arbitrary character at the beginning are OK (the first term), \nexcept the cases of some size-(n-1) good strings that starts with the last len(evil)-1 characters in evil \nand combines with the beginning character that happens to equal to evil[0] (the second term).\nThen, we know that a simple DP for S is not enough, we run a DP for the function C.\n\nThen, if m != 0, C(n, m) = C(n-1, m-1) for almost all the case, the intuition is that the first character must be the evil[-m], however, only one case that if the last evil[-m:] == evil[:m], then add the first character, evil[-m], may make the evil appear at the beginning of the string, then we must exclude the cases for C(n-1, len(evil)-1)\n\nAnd finally, back to the original problem. We must exclude the cases that smaller than s1 or greater than s2 from S(n).\n\n\nMaybe using KMP can accelerate the *get_match_head* function, however, my solusion is still faster than those with KMP.\n\n\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        cs  = \'abcdefghijklmnopqrstuvwxyz\'\n        c2i = {c:i for i, c in enumerate(cs)}\n        MMM = 10**9+7 \n\t\t# I tried some cases with NNN=10 locally, thus I can compare the results with naive search.\n        NNN = 26   \n\t\t\n\t\t# here is the DP for function C,  and we set C(n, 0) := S(n)\n        @functools.lru_cache(None)\n        def checkn_evil(n: int, m:int) -> int:\n            if m == n : return 1 # the only possible case is that x=eval[:m]\n            if m > n : return 0   #emmm, n is too small~\n\n            # the case for S(n)\n            if m == 0 : \n\t\t\t    # the evil is too big to be contained in a size-n string\n                if len(evil) > n : return NNN**n % MMM\n\t\t\t\t# hey! look at the evil! exclude it~\n                if len(evil) == n : return (NNN**n-1) % MMM\n\n\t\t\t\t# here is S(n) = 26 * S(n-1) - C(n-1, len(evil)-1)\n                to_ret = checkn_evil(n-1, 0)*NNN-checkn_evil(n-1, len(evil)-1)\n                return to_ret % MMM\n\t\t\t\t\n\t\t\t# the case for C(n, m)\n            else :\n                to_ret = checkn_evil(n-1, m-1)\n                if evil[:m]==evil[-m:] :\n                    to_ret -= checkn_evil(n-1, len(evil)-1)\n                return to_ret % MMM\n\n        # check  whether a suffix of evil is a prefix of the string, pre.\n        def get_match_head(pre, evil) :\n            to_ret = None\n            for i in range(min(len(pre), len(evil))) :\n                if evil[:i+1] == pre[-i-1:] :\n                    to_ret = i+1\n            return to_ret\n\n        \n        to_ret = checkn_evil(n, 0)\n\t\t\n\t\t# exclude the cases in S(n) that smaller than s1\n        for i in range(n) :\n            for j in range(c2i[s1[i]]) :\n\t\t\t    """\n\t\t\t\tif s1 == bcc, we exclude the cases that starts with a, ba, bb, bca, bcb orderly.\n\t\t\t\t"""\n                pre = s1[:i]+cs[j] # the prefix\n                if evil in pre :\n                    continue # if evil in pre, no cases to exclude\n\t\t\t\t\t\n                mt = checkn_evil(n-len(pre), 0)\n                match_head = get_match_head(pre, evil) \n                if not match_head is None :\n                    mt -= checkn_evil(n-len(pre), len(evil)-match_head)\n                to_ret -= mt\n\n\t\t# exclude the cases in S(n) that greater than s2, similar to the last section.\n        for i in range(n) :\n            for j in range(c2i[s2[i]]+1, len(cs)) :\n                pre = s2[:i]+cs[j]\n                if evil in pre :\n                    continue\n                mt = checkn_evil(n-len(pre), 0)\n\t\t\t\tmatch_head = get_match_head(pre, evil)\n                if not match_head is None :\n                    mt -= checkn_evil(n-len(pre), len(evil)-match_head)\n                to_ret -= mt\n\n\t\t# and the final answer\n        return to_ret % MMM\n```
[]