题意描述

动物园

动物园是个好地方

给出字符串 \(S\)，求 \(\sum_{i=1}^{|S|} num(i)\)，其中 \(num(i)\) 表示：

对于字符串 \(S\) 的前 \(i\) 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，

将这种字符串的数量记作 \(num(i)\)。

算法分析

首先可以看看在 KMP 中的 \(next\) 数组的定义：

对于字符串 \(S\) 的前 \(i\) 个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），

最长的长度记作 \(next[i]\)。

有眼睛的人都发现这两位的定义尤为相似，所以这道题可以利用 KMP 解决。

特别容易注意到的是一个特殊的条件 “该后缀与该前缀不重叠”，显然就是说 \(next(i)\leq i/2\)。

首先假设没有这个条件，那么 \(num(i)\) 在 KMP 的时候就可以求出来了，代码：

void get_nxt(){
	num[1]=1;
	for(int i=2,j=0;i<=len;i++){
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) ++j;
		nxt[i]=j;num[i]=num[j]+1;//KMP时顺便DP
	}
	return;
}

然后既然有 \(next(i)\leq i/2\) 这个条件，不妨多加个while(j>i/2) j=nxt[j]就好了。

然后在统计时顺便统计答案，省下空间。

代码实现

注意一下答案用long long存。（十年 OI 一场空）

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
#define mod 1000000007
using namespace std;

int n,nxt[N],num[N],len;
long long ans;
char s[N];

void get_nxt(){
	num[1]=1;
	for(int i=2,j=0;i<=len;i++){
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) ++j;
		nxt[i]=j;num[i]=num[j]+1;
	}
	return;
}

void get_num(){
	ans=1;
	for(int i=2,j=0;i<=len;i++){
		while(j && s[i]!=s[j+1]) j=nxt[j];
		if(s[i]==s[j+1]) j++;
		while(j>i/2) j=nxt[j];
		ans=(ans*(long long)(num[j]+1)) % mod;
	}
	printf("%lld\n",ans);
	return;
}

int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%s",s+1);
		len=strlen(s+1);
		get_nxt();
		get_num();
	}
	return 0;
}

完结撒花

P2375 [NOI2014]动物园

原文：https://www.cnblogs.com/lpf-666/p/12848966.html