动物园
题目描述
输入格式
输出格式
输入输出样例
输入
3
aaaaa
ab
abcababc
输出
36
1
32
开始时都没看出来这是kmp板子题
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
char a[maxn];
int len,p[maxn],num[maxn];
//num[i]表示从i跳border能跳多少次，与题中的num数组含义不同
void kmp()
{num[1]=1; len=strlen(a+1);for (int i=2,j=0;i<=len;i++){while (j&&a[j+1]!=a[i]) j=p[j];if (a[j+1]==a[i]) j++;p[i]=j;num[i]=num[j]+1;//递推 }
}
ll ans;
void solve()
{ans=1;for (int i=2,j=0;i<=len;i++){while (j&&a[i]!=a[j+1]) j=p[j];if (a[i]==a[j+1]) j++;while ((j<<1)>i) j=p[j];ans=ans*(num[j]+1)%mod;}printf("%lld\n",ans);
}
int main()
{int n;scanf("%d",&n);while (n--){scanf("%s",a+1);kmp();solve();}return 0;
}
注意事项
- num[i]表示从i跳border能跳多少次，与题中的num数组含义不同
从i跳border能跳多少次就表示可重叠的真前缀个数
（题目中表示不重叠的真前缀个数） - 查找时每次j都从上一次j<=(i/2)时继承（不然会T）
错误示范：
void solve()
{ans=1;for (int i=1;i<=len;i++){int j=i;//遇到hack数据aaaaaaaaaaaaaa时每次向前跳一次会Twhile ((j<<1)>i) j=p[j];ans=ans*(num[j]+1)%mod;}printf("%lld\n",ans);
}
正确示范：
void solve()
{ans=1;for (int i=2,j=0;i<=len;i++){while (j&&a[i]!=a[j+1]) j=p[j];if (a[i]==a[j+1]) j++;while ((j<<1)>i) j=p[j];ans=ans*(num[j]+1)%mod;}printf("%lld\n",ans);
}
如上图中15号位的j由14号位的j+1继承而来（虽然由于有重叠会往前跳但那是之后的事）
如果是错误代码则会从i开始一位一位往前跳时间复杂度太高会T
完结撒花！
