【KMP】动物园

字符串

传送门：UOJ5

思路一：

  • 先求出next数组；
  • 由于是计数，不是求最长长度，在求next的时候统计出每个点的border的总数cnt；
  • 然后对于原串的每个前缀，找到最大的大小不超过一半的border，num值就等于那个点的cnt+1；
  • 然后找大小不超过一半的border可以用类似于求next数组的方法，多加一个长度的限制条件。

注意：

  • 每次单独求会TLE；

思路二

似乎是找规律（待填坑）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define N 1200000
#define mod 1000000007
LL n,nxt[N],num[N],cnt[N];
char s[N];
LL kmp(char s[]){
	LL i=2,j=nxt[1]=0,ans=1;
	LL len=strlen(s+1);
	while (i<=len){
		while (j>=1 && s[i]!=s[j+1]) j=nxt[j];
		if (s[i]==s[j+1]){nxt[i]=++j; cnt[i]=cnt[j]+1;} else{nxt[i]=cnt[i]=0;} i++;
	}
	
	i=2,j=num[1]=0;
	while (i<=len){
		while ((j>=1 && s[i]!=s[j+1]) || j+1>i/2) j=nxt[j];
		if (s[i]==s[j+1]) num[i]=cnt[++j]+1; else num[i]=0; ans=ans*(num[i++]+1)%mod;
	}
	return ans;
}
	
int main(){
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%s",s+1);
		printf("%lld\n",kmp(s));
	}
	
	return 0;
}