KMP, c++
The whole idea is to proceed character by character and check if it is ok to proceed or not. KMP part is similar to needle in haystack problem. we need to do th
The whole idea is to proceed character by character and check if it is ok to proceed or not. KMP part is similar to needle in haystack problem. we need to do three checks, if so far we are larger than s1, if so far we are smaller than s2, and if we are building evil word by this new character. what evilpos shows? the position in KMP array for needle. So we are checking where we stand for the last character in terms of comparision.\n```\nclass Solution {\nprivate:\n    string s1,s2,evil;\n    vector<int> KMP;\n    int dp[500][50][2][2]={};\n    int calculate(int pos,int evilpos,bool s1equal, bool s2equal){\n        if(pos==s1.size())\n            return 1;\n        if(!dp[pos][evilpos][s1equal][s2equal]){\n            for(auto c=\'a\'; c<=\'z\';c++){\n                int curpos=evilpos;\n                while(c!=evil[curpos] && curpos>0) \n                    curpos=KMP[curpos-1];\n                if(c==evil[curpos]) curpos++;\n                if((s1equal && c<s1[pos]) || (s2equal && c>s2[pos]) || (curpos==evil.size()))\n                    continue;\n                else\n                {\n                    dp[pos][evilpos][s1equal][s2equal]=(dp[pos][evilpos][s1equal][s2equal]+calculate(pos+1,curpos,(s1equal && c==s1[pos]),s2equal && c==s2[pos])) % 1000000007;\n                }\n            }\n        }\n        return dp[pos][evilpos][s1equal][s2equal];\n    }\npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {   \n        this->s1=s1;\n        this->s2=s2;\n        this->evil=evil;\n        KMP.resize(evil.size(),0);\n        //build kmp of evil word\n        KMP[0]=0;\n        int k=0;\n        for(int i=1;i<evil.length();i++){\n            while(evil[i]!=evil[k] && k>0) k=KMP[k-1];\n            if(evil[i]==evil[k]) KMP[i]=++k;\n        }\n        return calculate(0,0,1,1);\n     }   \n    \n};\n```
['C']