2021.11.16 P2375 [NOI2014] 动物园（EXKMP+差分）

2021.11.16 P2375 [NOI2014] 动物园（EXKMP+差分）

https://www.luogu.com.cn/problem/P2375

题意：

PS：这道神题的背景让人疑惑，重点是当我飞快磨磨唧唧打出正确自认为正确的代码时，我第三个样例算出了144。讨论区一看，背景有大大的锅，哭了。

有n个字符串，对每个字符串S，设 num[i] 为 \(1 \dots i\) 的不重叠的相同的前缀和后缀的数量。

例如： abcababc 的 num 数组为 \(0,0,0,1,1,1,1,1\) 。

分析：

EXKMP求的是前缀与后缀的最长公共前缀。求出z数组后（我是从0开始求z数组的），对于第 i 位（此时从1开始计算），它所对应的z数组 z[i] 正好是从 i 位（从第0位开始计数的话）开始的后缀与从第0位开始的前缀的最长公共前缀。设 \(x=min(i,z[i])\) ， x 表示从第1位开始计数的第 i 位的长度为 i ，和从第0位开始计数的第 i 位的 z[i] 的长度的最小值。如： aaaaa 的z函数为

\[z_0=5,z_1=4,z_2=3,z_3=2,z_4=1
\]

当 i=1 时，z[1]=4 ，表示后四个a与整个字符串共同前缀最长为4，此时 \(x=min(1,4)=1\) ，表示第 i+x=2 位的 num[2] 增加1。根据题意，前缀与后缀不能重叠，所以最短的才是第 i+x 位的一个不重叠的公共的前缀与后缀的前缀。

当算出来第 i+x 位的 num 增加1时，根据z函数的定义，第 \(i+1 \dots i+x\) 位的 num 都增加了1。

例如： abcdabc 当 i=4 时，z[4]=3 ， \(x=min(4,3)=3\) ，求出来的是对第 i+x=4+3=7 位的 num 加1，但是同时我们也算出来了对 i+x-1=4+2=6 ，i+1=4+1=5 的 num 加1。

当我开心的写个了for循环搞定这一坨东西后，我发现，我“开心”地TLE了，只有可怜的50分，硬生生写了个kmp也有60分啊……

开始优化：差分是个好东西，把原来最差循环时间复杂度为 \(O(n/2)\) 的立马变为一加一减。

OK，恭喜你，AC这道我第一次见的时候还是紫题的蓝题。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=1e6+10;

const int mod=1e9+7;

typedef long long ll;

int n,z[N],nexti[N];

char s[N];

inline void getz(char *s){

	int len=strlen(s);

	z[0]=len;

	for(int i=1,l=0,r=0;i<len;i++){

		if(i<=r)z[i]=min(z[i-l+1-1],r-i+1);

		while(i+z[i]<len&&s[z[i]-1+1]==s[i+z[i]-1+1])++z[i];

		if(i+z[i]-1>r)l=i,r=i+z[i]-1;

	}

	//for(int i=0;i<=len;i++)cout<<z[i]<<" ";cout<<endl;

}

int main(){

	cin>>n;

	while(n--){

		memset(z,0,sizeof(z));

		memset(nexti,0,sizeof(nexti));

		scanf("%s",s);

		getz(s);

		int len=strlen(s);

		for(int i=1;i<=len;i++){

			int x=min(z[i],i);

			++nexti[i+1];--nexti[i+x+1];

			//for(int j=i+x;j>i;j--)++nexti[j];

		}

		//for(int i=len-1;i>=1;i--)nexti[i]=max(nexti[i+1]-1,nexti[i]);

		ll ans=(nexti[1]+nexti[0]+1);

		for(int i=2;i<=len;i++)nexti[i]+=nexti[i-1],ans=ans*(nexti[i]+1)%mod;

		//for(int i=1;i<=len;i++)cout<<nexti[i]<<" ";cout<<endl;

		cout<<ans<<endl;

	}

	return 0;

}

2021.11.16 P2375 [NOI2014] 动物园（EXKMP+差分）的相关教程结束。