Digit Dp + KMP algorithm
\n\n# Complexity\n- Time complexity:O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(nm)\n Add your space complexity here, e.g. O(n) \n
\n\n# Complexity\n- Time complexity:O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n*m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\nint mod=1e9+7;\nvector<int> Lps;\nint n,e;\nstring s1,s2,evil;\nint dp[501][51][2][2];\n vector<int> getLps(string s) {\n     int m=s.size();\n\n     int i=1;\n     vector<int> lps(m,0);\n     int len=0;\n\n     lps[0]=0;\n     while(i<m){\n         if(s[i]==s[len]){\n             len++;\n             lps[i]=len;\n             i++;\n         }\n         else{\n             if(len>0){\n                 len=lps[len-1];\n             }\n             else{\n                 lps[i]=0;\n                 i++;\n             }\n         }\n     }\n\n     return lps;\n    }\n    int solve(int index,int eindex,bool tight1,bool tight2){\n        if(eindex>=e)\n        return 0;\n        if(index>=n)\n        return 1;\n        if(dp[index][eindex][tight1][tight2]!=-1)\n        return dp[index][eindex][tight1][tight2];\n\n        char lo=tight1?s1[index]:\'a\';\n        char hi=tight2?s2[index]:\'z\';\n         int ans=0;\n        for(char ch=lo;ch<=hi;ch++){\n            int nxtIndex=eindex;\n\n            while(evil[nxtIndex]!=ch && nxtIndex>0)\n            nxtIndex=Lps[nxtIndex-1];\n\n            if(nxtIndex!=0){\n                ans=(ans%mod+solve(index+1,nxtIndex+1,tight1&&ch==lo,tight2&&ch==hi)%mod)%mod;\n            }\n            else{\n                if(evil[nxtIndex]==ch)\n                 ans=(ans%mod+solve(index+1,1,tight1&&ch==lo,tight2&&ch==hi)%mod)%mod;\n                 else\n                  ans=(ans%mod+solve(index+1,0,tight1&&ch==lo,tight2&&ch==hi)%mod)%mod;\n            }\n        }\n        return dp[index][eindex][tight1][tight2]=ans;\n    }\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        this->Lps=getLps(evil);\n        this->n=n;\n        this->e=evil.size();\n        this->s1=s1;\n        this->s2=s2;\n        this->evil=evil;\n        memset(dp,-1,sizeof(dp));\n        return solve(0,0,1,1)%mod;\n }\n};\n```
['String', 'Dynamic Programming', 'String Matching', 'C++']