Digit Dp + Kmp C++ Solution
\nconst int mod = 1e9 + 7;\nconst int NX = 55;\nint totalLength, evilLength;\nint evilT[ NX ];\nint dp[ 502 ][ 2 ][ 2 ][ 52 ];\nstring small, big, bad;\n\nint D
```\nconst int mod = 1e9 + 7;\nconst int NX = 55;\nint totalLength, evilLength;\nint evilT[ NX ];\nint dp[ 502 ][ 2 ][ 2 ][ 52 ];\nstring small, big, bad;\n\nint DP( int pos, int isSmall, int isBigger, int matchSoFarEvil) { \n    if( evilLength == matchSoFarEvil ) { \n        return 0;\n    }\n    if( totalLength == pos ) { \n        return 1;\n    }    \n    \n    int &ret = dp[ pos ][ isSmall ][ isBigger ][ matchSoFarEvil ];\n    if( ret != -1 ) return ret;\n    ret = 0;\n    int start = isBigger == 0 ? small[pos] - \'a\' : 0;\n    int end = isSmall == 0 ? big[pos] - \'a\' : 25;\n    \n    for( int i = start ; i <= end ; i++ ) { \n        int nxtMatchSoFarEvil = matchSoFarEvil;\n        int nowEvail = bad[matchSoFarEvil] - \'a\' ;\n        while( nxtMatchSoFarEvil > 0 && (bad[nxtMatchSoFarEvil] - \'a\') != i ) { \n            nxtMatchSoFarEvil = evilT[nxtMatchSoFarEvil];\n        }\n        if( i == bad[nxtMatchSoFarEvil] - \'a\' ) nxtMatchSoFarEvil++;\n       \n        int nxtIsSmall = isSmall || (big[pos] - \'a\' > i );\n        int nxtIsBigger = isBigger || (small[pos] - \'a\' < i );\n        ret += DP( pos + 1 , nxtIsSmall,  nxtIsBigger, nxtMatchSoFarEvil) % mod;\n        ret %= mod;\n       \n    }\n    return ret;\n\n}\n\nclass Solution {\npublic:\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        totalLength = n;\n        small = s1;\n        big = s2;\n        bad = evil;\n        evilLength = evil.size();\n        evilT[0] = 0;\n        evilT[1] = 0;\n        int k = 0;\n        for( int i = 0 ; i <= totalLength ; i++ ) { \n            for( int j = 0 ; j < 2 ; j++ ) { \n                for( int k = 0 ; k < 2 ; k++ ) { \n                    for( int l = 0 ; l <= evilLength ; l++ ) {\n                        dp[i][j][k][l] = -1;\n                    }\n                }\n            }\n        }\n        for( int idx = 2; idx <= evil.size() ; idx++ ) { \n            while( k > 0 && evil[k] != evil[idx-1] ) k = evilT[k];\n            if(evil[k] == evil[idx-1]) k++;\n            evilT[idx] = k;\n        }\n        return DP( 0 , 0 , 0 , 0 );\n    }\n};\n```
[]