KMP+Digit DP
```\nclass Solution {\npublic:\n    int kmp[51];\n    int dp[2][2][51][501];\n    int n,m;\n    string L,R,bad;\n    const int mod=1e9+7;\n    int rec(int lev,i
```\nclass Solution {\npublic:\n    int kmp[51];\n    int dp[2][2][51][501];\n    int n,m;\n    string L,R,bad;\n    const int mod=1e9+7;\n    int rec(int lev,int tlo,int thi,int match){\n        if(match==m) return 0;\n        if(lev==n) return 1;\n        int &ans = dp[tlo][thi][match][lev];\n        if(ans!=-1) return ans;\n        ans=0;\n        int lo=0,hi=25;\n        if(tlo==1) lo=L[lev]-\'a\';\n        if(thi==1) hi=R[lev]-\'a\';\n        for(int i=lo;i<=hi;i++){\n            int ntlo=tlo,nthi=thi;\n            if(i!=L[lev]-\'a\')ntlo=0;\n            if(i!=R[lev]-\'a\')nthi=0;\n            int nxt = match;\n            while(nxt > 0 && bad[nxt]!=i+\'a\')nxt=kmp[nxt];\n            if(i+\'a\'==bad[nxt])nxt++;\n            (ans+=rec(lev+1,ntlo,nthi,nxt))%=mod;\n        }\n        return ans;\n    }\n    int findGoodStrings(int N, string s1, string s2, string evil) {\n        memset(dp,-1,sizeof(dp));\n        L=s1,R=s2,bad=evil;\n        n=L.length();m=bad.length();\n        kmp[0]=-1;\n        int i=0,j=-1;\n        while(i<m){\n            while(j!=-1 && bad[i]!=bad[j])j=kmp[j];\n            i++;j++;\n            kmp[i]=j;\n        }\n        return rec(0,1,1,0);\n    }\n};
[]