Classic Digit DP problem with KMP
Intuition\nThis is an excellent problem to demonstrate KMP being an online algorithm ie, we do not need entire string to run the matching algorithm, instead we 
# Intuition\nThis is an excellent problem to demonstrate KMP being an online algorithm ie, we do not need entire string to run the matching algorithm, instead we can incrementaly keep on comparing with each incoming characters untill we match the entire pattern.\n\nDigit DP is popular way to generate numbers between two intervals one character at a time with certain property.\n\nUsing this two facts, We can start generating numbers one character at a time and keep on checking how many of the last k characters added to the string matches the (first k characters of) evil string. \n\n# Complexity\n- Time complexity:\n-  $$O(N * size(evil))$$\n\n- Space complexity:\n- $$O(N * size(evil))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int mod = 1e9 + 7;\n    string ss, se, ev;\n    vector<int> lps;\n    int dp[501][51];\n\n    int solve(int pos, int evil_len, int lo, int hi) {\n        if(evil_len == ev.size()) return 0; // prunning is done here since no need is there to explore rest of the string, since it wont contribute to result\n        if(pos == ss.size()) return 1;\n\n        int& val = dp[pos][evil_len];\n        if((!lo && !hi) && val != -1) return val;\n\n        int count = 0;\n        char low = lo ? ss[pos] : \'a\';\n        char high = hi ? se[pos] : \'z\';\n\n        for(char i=low; i<=high; ++i) {\n            int j = evil_len;\n            while(j > 0 && ev[j] != i)\n                j = lps[j-1];\n            if(ev[j] == i) j++;\n            count = (count + solve(pos + 1, j, lo & (i == ss[pos]), hi & (i == se[pos]))) % mod;\n        } \n\n        return lo || hi ? count : val = count; \n    }\n\n    int findGoodStrings(int n, string s1, string s2, string evil) {\n        lps.assign(evil.size(), 0);\n        ss = s1, se = s2, ev = evil;\n\n        int j;\n        for(int i=1; i<evil.size(); ++i) {\n            j = lps[i-1];\n            while(j > 0 && evil[i] != evil[j])\n                j = lps[j-1];\n\n            if(evil[i] == evil[j]) j++;\n            lps[i] = j;\n        }\n\n        memset(dp, -1, sizeof(dp));\n        \n        return solve(0, 0, 1, 1);\n    }\n};\n```
['Dynamic Programming', 'C++']