1397. Find All Good Strings.cpp
Code\n\nclass Solution {\npublic:\n    const int mod=1E9+7;\n    typedef vector<int> PI;\n    typedef vector<PI> PII;\n    typedef vector<PII> PIII;\n    typede
**Code**\n```\nclass Solution {\npublic:\n    const int mod=1E9+7;\n    typedef vector<int> PI;\n    typedef vector<PI> PII;\n    typedef vector<PII> PIII;\n    typedef vector<PIII> PIIII;\n    PIIII dp;\n    PI table;\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        int m=evil.size();\n        dp=PIIII(n,PIII(m,PII(2,PI(2,-1))));\n        table=vector<int>(m);\n        int i=1;\n        int len=0;\n        while(i<m){\n            if(evil[len]==evil[i]){\n                len++;\n                table[i]=len;\n                i++;\n            }else{\n                if(len==0){\n                    table[i]=0;\n                    i++;\n                }else{\n                    len=table[len-1];\n                }\n            }\n        }\n        return dfs(0,0,1,1,n,s1,s2,evil);\n    }\n    \n    int dfs(int i, int j, int follow1, int follow2, int n, string& s1, string& s2, string& evil){\n        if(j==evil.size()) return 0;\n        if(i==n) return 1;\n        if(dp[i][j][follow1][follow2]!=-1) return dp[i][j][follow1][follow2];\n            \n        long long res=0;\n        for(char c=\'a\';c<=\'z\';c++){\n            int nj=j;\n            while(nj>0 && evil[nj]!=c) nj=table[nj-1];\n            if(evil[nj]==c) nj++;\n            else nj=0;\n            int nfollow1=follow1;\n            int nfollow2=follow2;\n            if(follow1==1 && follow2==1){\n                if(c>=s1[i] && c<=s2[i]){\n                    nfollow1=(c==s1[i])?1:0;\n                    nfollow2=(c==s2[i])?1:0;\n                    res+=dfs(i+1,nj,nfollow1,nfollow2,n,s1,s2,evil);\n                }\n            }else if(follow1==1 && follow2==0){\n                if(c>=s1[i]){\n                    nfollow1=(c==s1[i])?1:0;\n                    res+=dfs(i+1,nj,nfollow1,nfollow2,n,s1,s2,evil);\n                }\n            }else if(follow1==0 && follow2==1){\n                if(c<=s2[i]){\n                    nfollow2=(c==s2[i])?1:0;\n                    res+=dfs(i+1,nj,nfollow1,nfollow2,n,s1,s2,evil);\n                }\n            }else{\n                res+=dfs(i+1,nj,nfollow1,nfollow2,n,s1,s2,evil);\n            }\n            res%=mod;\n        }\n        return dp[i][j][follow1][follow2]=res;\n    }\n};\n```
['C']