DP WITHOUT KMP (Python 140ms)
Let\'s break this question up into several steps:\n\n1. Define the auxiliary function f(s): it counts the number of strings that are less than or equal to s, an
Let\'s break this question up into several steps:\n\n1. Define the auxiliary function f(s): it counts the number of strings that are less than or equal to s, and doesn\'t contain evil as a substring. Then the original question is equal to f(s2) - f(s1) + (evil not in s1).\n2.  To compute f(s), it suffices to define two more functions, \ncount(s): it computes the number of strings that are less than or equal to s.\nhelper(s): it computes the number of strings that are less than or equal to s, and contains evil as a substring.\nThen f(s) = count(s) - helper(s)\n3. count(s) is easy to compute. Let\'s start with an analogy: how many non-negative integers are <= 2312359? It is just 2312359 + 1. (the additional 1 corresponds to 0). Back to strings, we can think of s as a 26-bit integer, and count(s) is just it\'s value plus one. The code is as follows:\n\n\'\'\'\n\n\tdef count(s):\n\t\tans = 0\n\t\tfor x in s:\n\t\t\tans = (26*ans + ord(x) - ord(\'a\')) % mod\n\t\treturn (ans + 1)%mod \n\'\'\'\n4. It all boils down to computing helper(s), this is where DP comes in. We further break down the computation of helper(s) into three numbers:\nFor those strings <= s, and of same length as s,\na: counts the number of strings t, with prefix = evil, i.e. t = evil + t[len(evil):].\nb: counts the number of strings t, such that t[1:] contains evil.\nc: counts the number of strings t with prefix = evil, and t[1:] contains evil.\nBy incllusion exclusion principle: helper(s) = a + b - c.\n\nThe full code is as follows:\n\n\'\'\'\n\n\n\tfrom functools import lru_cache\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        mod = 10**9 + 7\n        pov = [1]\n        for _ in range(n+1):\n            pov.append((pov[-1]*26) % mod)\n        \n        \n        m = len(evil)\n        print(m, pov)\n        @lru_cache(None)\n        def helper(s): # compute how many <= s and contains evil\n            l = len(s)\n            if l < m:\n                return 0\n            if l == m:\n                if s < evil:\n                    return 0\n                else:\n                    return 1\n            \n            b = (ord(s[0]) - ord(\'a\'))*helper(\'z\'*(l-1)) % mod + helper(s[1:]) % mod\n            if s[:m] < evil:\n                return b\n            else:\n                if s[:m] == evil:\n                    a = count(s[m:])\n                    c = helper(evil[1:] + s[m:]) - helper(evil[1:] + \'a\'*(l - m)) + (evil in (evil[1:] + \'a\'*(l - m)))\n                else:\n                    a = pov[l - m]\n                    c = helper(evil[1:] + \'z\'*(l - m)) - helper(evil[1:] + \'a\'*(l - m)) + (evil in (evil[1:] + \'a\'*(l - m)))\n                \n                return (a + b - c) % mod\n        @lru_cache(None) \n        def count(s):\n            ans = 0\n            for x in s:\n                ans = (26*ans + ord(x) - ord(\'a\')) % mod\n            return (ans + 1)%mod \n\n        res = count(s2) - helper(s2) - (count(s1) - helper(s1))\n        if evil not in s1:\n            res +=1\n        return res % mod\n\n\n\'\'\'\n\nI also have the same implementation in C++, however, as a beginner for C++, I constantly get wrong answers, it would be highly appreciated if someone can point out my mistake. (**I realized what the mistake is, and modifying it accordingly, it turns out a + b == c means (a+b) == c, one should really make sure the arithmetic order...**)\n\nHowever, the C++ version seems to be significantly slower relative to other C++ solution, any idea on why is it?\n\'\'\'\nclass Solution {\n\n    int mod = pow(10, 9) + 7, m;\n    vector<long> power{1};\n    unordered_map<string, long> dic;\n\n\npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n\n        \n        for (int i = 0; i < n + 1; i++){\n            power.push_back((power.back()*26) % mod);\n        }\n        m = evil.size();\n\n        \n        long ans =  (count(s2) - helper(s2, evil) - (count(s1) - helper(s1, evil)))%mod;\n        if (s1.find(evil) == string::npos) ans ++;\n        return (ans < 0) ? ans + mod: ans%mod;\n    }\n    \n    \n    long count(string s){\n        long ans = 0;\n        for (auto x: s){\n            ans = (ans*26 + (x - \'a\')) % mod;\n        }\n        return (ans + 1) % mod;\n    }\n\n    long helper(string s, string& e){\n        if (dic.find(s) != dic.end()) return dic[s];\n        \n        int l = s.size();\n        long a, b, c;\n        if (l < m) return 0;\n        if (l == m) return e <= s ? 1 : 0;\n        \n        b = (helper(s.substr(1), e) + (s[0] - \'a\')*helper(string(l-1, \'z\'), e)) % mod;\n        \n        if (s.substr(0, m) < e){\n            dic[s] = b;\n            return b ;\n        }\n        if (s.substr(0, m) == e){\n            a = count(s.substr(m));\n            c = (helper( e.substr(1) + s.substr(m), e) - helper(e.substr(1) + string(l - m,\'a\'), e)) % mod;\n            if ((e.substr(1) + string(l - m, \'a\')).find(e) != string::npos) c++;\n        }\n        else{\n            a = power[l - m];\n            c = (helper(e.substr(1) + string(l - m, \'z\'), e) - helper(e.substr(1) + string(l-m,\'a\'), e)) % mod;\n            if ((e.substr(1) + string(l-m,\'a\')).find(e) != string::npos) c++;\n        }\n\n        \n        dic[s] = (a + b - c) % mod;\n        return dic[s];\n    \n    }\n\n};\n\n\'\'\'
[]