bzoj3670:[Noi2014]动物园(KMP)

Author Avatar
Sakits 8月 01, 2018

题解

  现在才来写这题…不过这题居然自己YY出来怎么做了…
  之前从来没有看过题解,虽然一开始交了两发复杂度假的下了数据才发现错…但最后还是想出复杂度对的辣!
  先跑一遍求失配函数,那个numnum实际上就是求长度不过ii一半的failfail有几个,所以先预处理出KMP上每个节点到KMP树根的距离,跑到合法位置就可以O(1)O(1)得到numnum了。
  一开始复杂度错的原因就是对每个ii都跑了一次找不过半位置的过程…可以发现这个显然是可以继承的,因为多一位之后的不过半位置一定只会更靠后。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1000010, inf=1e9, mod=1e9+7;
int n, Q;
int f[maxn], len[maxn];
char s[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void getfail()
{
	int j;
	for(int i=2;i<=n;i++)
	{
		for(j=f[i-1];j && s[j+1]!=s[i];j=f[j]);
		if(s[j+1]==s[i]) f[i]=j+1; else f[i]=0;
	}
}
 
int main()
{
	read(Q);
	while(Q--)
	{
		scanf("%s", s+1); n=strlen(s+1);
		getfail();
		for(int i=1;i<=n;i++) len[i]=len[f[i]]+1;
		int ans=1; int j=0;
		for(int i=1;i<=n;i++)
		{
			for(;j && s[j+1]!=s[i];j=f[j]);
			if(s[j+1]==s[i]) j++; else j=0;
			while(j*2>i) j=f[j];
			ans=1ll*ans*(len[j]+1)%mod;
		}
		printf("%d\n", ans);
	}
}