其实不用kmp也能过，简单优化一下get函数就行，当然肯定没有加上kmp快

class Solution {
public:
    const int MOD=1e9+7;
    string e;
    vector<string> v;//v[i]表示evil字符串前i个字符组成的字串
    int findGoodStrings(int n, string s1, string s2, string evil) {
        e=evil;
        v=vector<string>(55);
        v[0]="";
        for(int i=1;i<e.size();i++) v[i]=e.substr(0,i);

        int x=count(s2),y=count(s1),ans=0;
        if(s1.find(e)<s1.size()) ans=(x-y)%MOD;
        else ans=(x-y+1)%MOD;

        return (ans%MOD+MOD)%MOD;
    }
    int get(int j,char c)//若当前匹配到j个字符，且要加上字符c，那么计算新的匹配字符数，并返回
    {
        if(e[j]==c) return j+1;
        string str=v[j]+c;
        for(int i=j-1;i>=0;i--)
            if(e[i]==c&&v[i+1]==str.substr(str.size()-i-1)) return i+1;
        return 0;
    }
    int count(string s)//返回值为字符串
    {
        int n=s.size();
        //f[i][j][k]表示已经拿了i个字符，并且匹配了evil末尾的j个字符,k为1表示已经比s小了
        int f[510][55][2]={0}; 
        f[0][0][0]=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<e.size()&&j<=i;j++)
            {
                int x=f[i][j][0];
                for(char c='a';x&&c<=s[i];c++)
                {
                    if(c==s[i]) (f[i+1][get(j,c)][0]+=x)%=MOD;
                    else (f[i+1][get(j,c)][1]+=x)%=MOD;
                }
                x=f[i][j][1];
                if(!x) continue;
                for(char c='a';c<='z';c++)
                {
                    (f[i+1][get(j,c)][1]+=x)%=MOD;
                }
            }
        int res=0;
        for(int j=0;j<e.size();j++)
            for(int k=0;k<2;k++)
                (res+=f[n][j][k])%=MOD;
        return res;
    }
};