[C++] DP & KMP
\nclass Solution {\npublic:\n    long long mod  = 1000000007;\n    long long dp[505][2][55];\n    int kmp[55] = {};\n    \n    long long solve(string &s, string
```\nclass Solution {\npublic:\n    long long mod  = 1000000007;\n    long long dp[505][2][55];\n    int kmp[55] = {};\n    \n    long long solve(string &s, string &evil, int ind, int tight, int pre)\n    {\n        int n = s.size(), m = evil.size();\n        if(pre == m) return 0;\n        if(ind == n) return 1;\n        if(dp[ind][tight][pre] != -1) return dp[ind][tight][pre];\n        int k = 25;\n        if(tight) k = s[ind] - \'a\';\n        \n        long long ans = 0;\n        \n        for(int i=0; i<=k; i++)\n        {\n            int newtight = 0;\n            if(tight && k==i) newtight = 1;\n            int newpre = pre;\n            while(newpre>0 && i!=evil[newpre]-\'a\') newpre = kmp[newpre - 1];\n            if(i==evil[newpre]-\'a\') newpre++;\n            ans = (ans + solve(s, evil, ind+1, newtight, newpre))%mod;\n        }\n        return dp[ind][tight][pre] = ans;\n    }\n    \n    \n  \n    \n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        int m = evil.length();\n        for(int i=1; i<m; i++)\n        {\n            int j = kmp[i-1];\n            while(j>0 && evil[j]!=evil[i]) j = kmp[j-1];\n            if(evil[i]==evil[j]) j++;\n            kmp[i] = j;\n        }\n        memset(dp,-1,sizeof dp);\n        long long ans1 = solve(s1, evil, 0, 1, 0);\n         memset(dp,-1,sizeof dp);\n        long long ans2 = solve(s2, evil, 0, 1, 0);\n        long long ans = (ans2 - ans1 + mod)%mod;\n        int j = 0;\n        \n        //check if s1 is a good string\n        bool flag = true;\n        for(int i=0; i<n; i++)\n        {\n            while(j>0 && s1[i]!=evil[j]) j=kmp[j-1];\n            if(s1[i]==evil[j]) j++;\n            if(j==m) \n            {\n                flag = false;\n                break;\n            }\n        }\n        if(flag) ans = (ans + 1)%mod;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C']