c++ dp with KMP
follow1 / follow 2 means the established string follow along s1 / s2.\nAt start, follow1=follow2=1.\nFor instance, s1 = "leetcode", s2 = "leetgoes". When i get 
follow1 / follow 2 means the established string follow along s1 / s2.\nAt start, follow1=follow2=1.\nFor instance, s1 = "leetcode", s2 = "leetgoes". When i get to 4, we must make sure the current char>=\'c\' and <=\'g\'. If we add \'c\' here, then follow1=1, follow2=0, then i go to 5, we must make sure current char >=\'o\'. \ndp[i][j][follow1][follow2]: the good string arrives at i, the idx of evil is j, how many strings we can get.\nUsing KMP to find if the evil string matches some substring our established string.\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```
[]