解题报告：这道题好像是挺裸的kmp算法吧，我不太懂，之前学过hh,于是去回看了一遍y总的视频，可恶，然后明白了kmp的大致思路，如果暴力枚举字符串是否匹配的话挺难办的复杂度O(n^2),kmp的思路是预处理出来ne数组，ne数组的下标代表以它为结尾的，他的值代表的是最长前缀和后缀相等的部分，如果匹配不上把j更新成ne[j]，注意一点就是如果匹配上了j也要更新成ne[j]，用来方便下次匹配。
这题是群主发的，，，我一开始以为很难，以为要一个字符串字符串来做，但是后来发现原来只要用最短的字符串去匹配就好啦，因为如果不是最小的长度的话匹配值肯定是0,0乘以任何数都是0啊，这样只要处理最小的长度的kmp乘积就可以了，string下标从0开始要用另外一个模板，挺蛋疼的，我也没咋掌握，还好yxc发了两个版本的，%%%y总，然后这个模板ne[0]要变成1否则会死循环（你可以试试），因为j从-1开始的。
#include<iostream>
using namespace std;
const int N=1000010;
string s[N];
int ne[N*2];
const long long mod=998244353;
long long kmp(int t,int idx)
{
long long ans=0;
for(int i=0,j=-1;i<s[t].length();i++)
{
while(j>=0&&s[t][i]!=s[idx][j+1]) j=ne[j];
if(s[t][i]==s[idx][j+1]) {
//cout<<s[t][i]<<' '<<s[idx][j+1]<<endl;
j++;
}
//cout<<i<<' '<<j<<endl;
if(j==s[idx].length()-1)
{
ans++;
j=ne[j];
}
}
return ans;
// cout<<ans<<endl;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
cin>>s[i];
int minv=1e9;
int idx;
for(int i=0;i<n;i++)
{
if(s[i].length()<minv)
{
minv=s[i].length();
idx=i;
}
}
ne[0]=-1;
string p=s[idx];
for(int i=1,j=-1;i<p.length();i++)
{
while(j>=0&&s[idx][i]!=s[idx][j+1]) j=ne[j];
if(s[idx][i]==s[idx][j+1]) j++;
ne[i]=j;
}
// cout<<idx<<endl;
long long res=1;
for(int j=0;j<n;j++)
{
res=res%mod*kmp(j,idx)%mod;
if(res==0)
break;
}
for(int i=0;i<n;i++)
{
if(s[i].length()>s[idx].length())
printf("0\n");
else
{
printf("%lld\n",res);
}
}
return 0;
}
京公网安备 11010502036488号