题解 | #[模板]KMP字符串匹配#

第二题题解：

1. 首先长字符串肯定不是短字符串的子串。所以先找到最短的的那个字符串，设为a，所有长于a的字符串的结果都是0。

2. 还剩下和a同样长的字符串，他们与a的关系只有相等和不等两种，那么就发现一个性质：

• 如果存在一个字符串s，a不是s的子串，那么所有字符串的结果都是0。对于和a同样长的字符串b，如果a==b，那么b也不是s的子串，结果为0；如果a!=b，那么b不是a的子串，结果也为零。所以所有字符串的结果都为零。

• 对于任意一个字符串s，a都是s的子串，那么所有与a相同长度的字符串b的结果都和a相同。因为a是b的子串且a和b长度相同，因此a==b，故a,b结果相同，用kmp求出a对应的结果即可。

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
#define int ll
const int N=2e6+500;
const int mod=998244353;
int n,nt[N];
string s[N];

void makeNxt(string a){
    a=" "+a;
    nt[1]=0;
    for(int i=2,j=0;i<a.size();++i){
        while(j&&a[i]!=a[j+1]) j=nt[j];
        if(a[i]==a[j+1]) j++;
        nt[i]=j;
    }
}
int kmp(string s,string a){
    s=" "+s;
    a=" "+a;
    int cnt=0;
    for(int i=1,j=0;i<s.size();++i){
        while(j&&s[i]!=a[j+1]) j=nt[j];
        if(s[i]==a[j+1]) j++;
        if(j==a.size()-1){
            cnt++;
            j=nt[j];
        }
    }
    return cnt;
}
int slove(int x){
    makeNxt(s[x]);
    int res=1;
    for(int i=1;i<=n;++i){
        res=res*kmp(s[i],s[x])%mod;
    }
    return res;
}
signed main(){
    cin>>n;
    int len=0x3f3f3f3f;
    for(int i=1;i<=n;++i) cin>>s[i],len=min(len,int(s[i].size()));
    bool jud=false;
    int ans=0;
    for(int i=1;i<=n;++i){
        if(s[i].size()>len){
            printf("0\n");
            continue;
        }
        if(!jud){
            ans=slove(i)%mod;
            jud=true;
        }
        printf("%lld\n",ans);
    }
    system("pause");
}