time: O(m*n), space: O(n), fastest, a little math with DP, no recursive
\nconst mod = int(1e9+7)\n\nfunc findGoodStrings(n int, s1 string, s2 string, evil string) int {\n    m := len(evil)\n    lps := make([]int, m)\n    j := 0\n   
```\nconst mod = int(1e9+7)\n\nfunc findGoodStrings(n int, s1 string, s2 string, evil string) int {\n    m := len(evil)\n    lps := make([]int, m)\n    j := 0\n    for i := 1; i < m; i++{\n        for j > 0 && evil[i] != evil[j] {j = lps[j-1]}\n        \n        if evil[i] == evil[j] {j++; lps[i] = j}\n    }\n    \n    rep := m-lps[m-1] //repeat evil every rep chs\n    \n    n++\n    goodStringsCnt := func(s string, includeFit bool)int{\n        dpNotEvil := make([]bool, n) //dpFit[i] = if s[:i] is NOT evil\n        dpNotEvil[0] = true\n        \n        dpLess := make([]int, n) //dpLess[i] = all combinations less than s[:i]\n        \n        dpEvilInLess := make([]int, n) //dpEvilInLess[i] = evil combinations less than s[:i]\n        \n        for i := 1; i < n; i++{\n            previ := i-1\n            if dpNotEvil[i] = dpNotEvil[previ]; dpNotEvil[i] {\n                dpLess[i] = (int(s[previ]-\'a\')+dpLess[previ]*26) % mod //26 carry \n            }else{\n                dpLess[i] = (dpLess[previ]*26) % mod\n            }\n            \n            if i >= m {\n                mib := i-m //m indices before i\n\n                if dpNotEvil[i] && s[mib:i] == evil {dpNotEvil[i] = false} //update evil status\n                \n                if dpNotEvil[mib] && s[mib:i] > evil{ //should include upper bound since dpLess[i] is not include s[:i]\n                    if dpEvilInLess[i] = 1+dpLess[mib]; dpEvilInLess[i] >= mod {dpEvilInLess[i] -= mod}\n                }else{\n                    dpEvilInLess[i] = dpLess[mib]   \n                }\n                \n                if rep < m { //subtract cnt of dpEvilInLess already cut at step i-rep\n                    if dpEvilInLess[i] -= dpEvilInLess[i-rep]; dpEvilInLess[i] < 0 {dpEvilInLess[i] += mod}\n                }\n                \n                if dpLess[i] -= dpEvilInLess[i]; dpLess[i] < 0 {dpLess[i] += mod}\n            }\n        }\n        \n        if includeFit && dpNotEvil[len(s)]{\n            if dpLess[len(s)]++; dpLess[len(s)] >= mod {dpLess[len(s)] -= mod}\n        }\n        \n        return dpLess[len(s)]\n    }\n    \n    //ans = combinations less than s2(exclude evil) subtracts combinations less than s2(exclude evil)\n    ans := goodStringsCnt(s2, true) - goodStringsCnt(s1, false)\n    \n    if ans < 0 {return ans+mod}\n    \n    return ans\n}\n```
[]