KMP+ string dp
\nstring dp is standard here, but kmp is tricky and essential\n\n# Code\n\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -
\nstring dp is standard here, but kmp is tricky and essential\n\n# Code\n```\nclass Solution:\n    def findGoodStrings(self, n: int, s1: str, s2: str, evil: str) -> int:\n        m = len(evil)\n        kmp = [0]*m\n        j = 0\n        for i in range(1,m):\n            while j and evil[i]!=evil[j]:\n                j = kmp[j-1]\n            if evil[i] == evil[j]:\n                j += 1\n            kmp[i] = j\n\n        @cache\n        def dp(i,j,tight1,tight2):\n            if j == m:return 0\n            if i == n:\n                return 1\n            a1 = ord(\'a\')\n            a2 = ord(\'z\')\n            if tight1:\n                a1 = ord(s1[i])\n            if tight2:\n                a2 = ord(s2[i])\n            res = 0\n            for k in range(a1,a2+1):\n                newl = chr(k)\n                nevil = 0\n                nt1 = False\n                nt2 = False\n                nj = j\n                while nj and evil[nj]!=newl:\n                    nj = kmp[nj-1]\n                if newl == evil[nj]:\n                    nj += 1\n                if k == a1:\n                    nt1 = True\n                if k == a2:\n                    nt2 = True\n                if j+nevil<m:\n                    res += dp(i+1,nj,tight1 and nt1,tight2 and nt2)\n            return res % (10**9+7)\n        return dp(0,0,True,True) % (10**9+7)\n                \n        \n```
['Python3']