Digits dp + KMP Algorithm ( 60ms) C++
\nclass Solution {\npublic:\n    int F[501][51][2]; // index - check evil - tight\n    int a,b,check,mod=1e9+7;\n    vector<int> A;\n    int Add(int f1,int f2)\
```\nclass Solution {\npublic:\n    int F[501][51][2]; // index - check evil - tight\n    int a,b,check,mod=1e9+7;\n    vector<int> A;\n    int Add(int f1,int f2)\n    {\n        return (f1+f2)>=mod ? f1+f2-mod : f1+f2;\n    }\n    int Sub(int f1,int f2)\n    {\n        return (f1>=f2) ? f1-f2 : f1-f2+mod;\n    }\n    int memoi(int index,int cur,int tight,string & s,string & evil)\n    {\n        if(cur==evil.size()) return 0;\n        if(index==s.size()) return 1;\n        if(F[index][cur][tight]!=-1) return F[index][cur][tight];\n        int k,curtight,sum=0,huy;\n        if(tight==1) k=int(s[index])-\'a\';\n        else k=25;\n        for(int i=0;i<=k;i++)\n        {\n            if(tight==1&&i==int(s[index])-\'a\') curtight=1;\n            else curtight=0;\n            if(i==int(evil[cur])-\'a\') huy=cur+1;\n            else\n            {\n                if(cur==0) huy=0;\n                else\n                {\n                    int len=A[cur-1];\n                    while(1)\n                    {\n                        if(i==int(evil[len])-\'a\')\n                        {\n                            huy=len+1;\n                            break;\n                        }\n                        if(len==0)\n                        {\n                            huy=0;\n                            break;\n                        }\n                        if(i!=int(evil[len])-\'a\') len=A[len-1];\n                    }\n                }\n            }\n            sum=Add(sum,memoi(index+1,huy,curtight,s,evil));\n        }\n        return F[index][cur][tight]=sum;\n    }\n    bool CheckContain(string & s1,string & evil)\n    {\n        int len=0,x,y,dem=0;\n        A[0]=0;\n        for(int i=1;i<=evil.size()-1;i++)\n        {\n            while(1)\n            {\n                if(evil[i]==evil[len])\n                {\n                    A[i]=len+1;\n                    len++;\n                    break;\n                }\n                if(len==0)\n                {\n                    A[i]=0;\n                    break;\n                }\n                if(evil[i]!=evil[len]) len=A[len-1];\n            }\n        }\n        while(dem+evil.size()-1<=s1.size()-1)\n        {\n            y=0;\n            x=dem;\n            while(y<=evil.size()-1&&s1[x]==evil[y])\n            {\n                x++;\n                y++;\n            }\n            if(y!=evil.size()) dem=dem+A[y]+1;\n            else return false;\n        }\n        return true;\n    }\n    int findGoodStrings(int n, string & s1, string & s2, string & evil) {\n        A.resize(evil.size());\n        if(CheckContain(s1,evil)==true) check++;\n        memset(F,-1,sizeof(F));\n        a=memoi(0,0,1,s1,evil);\n        memset(F,-1,sizeof(F));\n        b=memoi(0,0,1,s2,evil);\n        return Add(Sub(b,a),check);\n    }\n};\n```
['C']