DIGIT DP + KMP
Intuition\n Describe your first thoughts on how to solve this problem. \nDigit DP for counting and KMP for string matching\n\n# Approach\n Describe your approac
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDigit DP for counting and KMP for string matching\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Count with the help of digit dp (i used <= count)\n2. Use KMP to adjust your j th pointer to match current string with the evil string for which you will require lps array of evil\n3. Subtract val2 and val1 and a +1 will be added only if the s1 string does not contain the substring evil (i.e apply kmp on this as well)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(2 X n X evil X 2)\n- Space complexity:\nO(2 X n X evil X 2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n### FEEL FREE TO COMMENT IN CASE OF DOUBTS\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int mod=1e9+7;\n    int dp[501][51][2];\n    vector<int>evilLPS;\n    vector<int> computeLPS(string &concatStr){\n        int size=concatStr.length();\n        vector<int>lps(size,0);\n\n        int len=0,i=1;\n        while(i<size){\n            if(concatStr[i]==concatStr[len]){\n                len++;\n                lps[i]=len;\n                i++;\n            }else{\n                if(len>0) len=lps[len-1];\n                else{\n                    lps[i]=0;\n                    i++;\n                }\n            }\n        }\n\n        return lps;\n    }\n\n    int count(int digits,int j,int constraint,string &num,string &evil){\n        if(j==evil.length()) return 0;\n        if(digits==0) return 1;\n\n        if(dp[digits][j][constraint]!=-1) return dp[digits][j][constraint];\n        long long int ans=0;\n\n        int len=num.length();\n        int ub=constraint?num[len-digits]-\'a\':25;\n\n        int evilDigit=(j==evil.length()?-1:evil[j]-\'a\');\n\n        for(int digit=0;digit<=ub;++digit){\n            int newInd=j;\n\n            while(digit!=(evil[newInd]-\'a\') && newInd>0){\n                newInd=evilLPS[newInd-1];\n            }            \n\n            if(digit==(evil[newInd]-\'a\')) newInd++;\n            \n            int val=count(digits-1,newInd,constraint & (digit==ub),num,evil);\n            val%=mod;\n            ans=(ans+val)%mod;\n        }\n\n        return dp[digits][j][constraint]=ans%mod;\n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        if(s1>s2) return 0;\n\n        evilLPS=computeLPS(evil);\n\n        memset(dp,-1,sizeof(dp));\n        int val1=count(n,0,1,s1,evil);\n        \n        memset(dp,-1,sizeof(dp));\n        int val2=count(n,0,1,s2,evil);\n\n        int addVal=1;\n        string concatStr=evil+\'$\'+s1;\n        vector<int>lps=computeLPS(concatStr);\n        for(int i=0;i<concatStr.length();++i){\n            if(lps[i]==evil.length()){\n                addVal=0;\n                break;\n            }\n        }\n\n        int ans=((val2+mod-val1)%mod+addVal)%mod;\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'String Matching', 'C++']