[python] top-down dp, O(n*len(veil)), 96% ~140ms
\n    def findGoodStrings(self, n, s1, s2, evil):\n        def funcc(s):\n            def func(i,k):\n                if d[i][k]==-1: d[i][k]=sum([func(i+1,x)*y
```\n    def findGoodStrings(self, n, s1, s2, evil):\n        def funcc(s):\n            def func(i,k):\n                if d[i][k]==-1: d[i][k]=sum([func(i+1,x)*y for x,y in dd[k]])%t\n                return d[i][k]\n            d,k,ans=[[-1]*(m+1) for _ in range(n+1)],0,0\n            for jj in range(m): d[n][jj]=1\n            for i in range(n+1): d[i][m]=0\n            for i in range(n):\n                p=ord(s[i])-ord(\'a\')\n                ans,k=ans+sum([func(i+1,a[k][j]) for j in range(p)]),a[k][p]\n                if k==m: break\n            return ans\n        m,t=len(evil),1000000007\n        a,b,d,dd=[[0]*26 for _ in range(m)],[-1]*(m+1),[0]*m,[]\n        for i in range(m):\n            for k in range(26):\n                d[i],j=k,b[i]\n                while j!=-1 and d[j]!=d[i]: j=b[j]\n                a[i][k]=j+1\n            p,q=ord(evil[i])-ord(\'a\'),{}\n            b[i+1],a[i][p],d[i]=a[i][p],i+1,p\n            for x in a[i]: q[x]=q.get(x,0)+1\n            dd.append([(x,q[x]) for x in q])\n        return (funcc(s2)-funcc(s1)+(evil not in s2))%t\n```\n\nI have to say this problem is a bit insane, at least for contest. However, compared to common view, I would argue it is actually a fairly good question for interview.\n1. KMP algorithm is preferred, but not necessary.\n    Essentially, for this problem, KMP algorithm is just a faster algorithm to the get longest prefix which is also a suffix for every index and every possible letter of evil. With a maximum evil.length of 50, even a normal O(26* n^3) approach would work.\n2. Top-down dp part is quite typical.\n3. While an O(26* n*len(veil)) solution would get accepted, opitmized solutions could make it much faster.
[]