dp with kmp
\nclass Solution {\npublic:\n    \n    void computeLps(string &evil,int len,vector<int>&lps){\n        int indx = 1;\n        int ln = 0;\n        lps[0] = 0;\n
```\nclass Solution {\npublic:\n    \n    void computeLps(string &evil,int len,vector<int>&lps){\n        int indx = 1;\n        int ln = 0;\n        lps[0] = 0;\n        while(indx<len){\n            if(evil[indx]==evil[ln]){\n                ln ++;\n                lps[indx] = ln;\n                indx ++;\n            }\n            else {\n                if(ln!=0){\n                    ln = lps[ln-1];\n                }\n                else {\n                    lps[indx] = 0;\n                    indx ++;\n                }\n            }\n        }\n    }\n    \n    int giveres(int pos,int pos2,int high_flag,int low_flag,int n,int len,string &s1,string &s2,string &evil,vector<vector<vector<vector<int>>>>&dp,vector<int>&lps,int mod = 1000000007){\n        if(pos2==len)\n            return 0;\n        if(pos==n)\n            return 1;\n        int &ret = dp[pos][pos2][high_flag][low_flag];\n        if(ret!=-1)\n            return ret;\n        ret = 0;\n        int low = 0,high = 25;\n        if(low_flag)\n            low = s1[pos]-\'a\';\n        if(high_flag)\n            high = s2[pos] - \'a\';\n        for(int i = low;i<=high;i++){\n            int xx = pos2;\n            while(i!=evil[xx]-\'a\'&&xx>0){\n                xx = lps[xx-1];\n            }\n            if(i==evil[xx]-\'a\'){\n                ret += giveres(pos+1,xx+1,high_flag&(i==s2[pos]-\'a\'),low_flag&(i==s1[pos]-\'a\'),n,len,s1,s2,evil,dp,lps);            }\n            else {\n                ret += giveres(pos+1,0,high_flag&(i==s2[pos]-\'a\'),low_flag&(i==s1[pos]-\'a\'),n,len,s1,s2,evil,dp,lps);\n            }\n            if(ret>=mod)\n                ret -= mod;\n        }\n        return ret;\n    }\n    \n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        int len = evil.size();\n        vector<vector<vector<vector<int>>>>dp(n+1,vector<vector<vector<int>>>(len+1,vector<vector<int>>(2,vector<int>(2,-1))));\n        vector<int>lps(len+1);\n        computeLps(evil,len,lps);\n        return giveres(0,0,1,1,n,len,s1,s2,evil,dp,lps);\n    }\n};\n```
[]