BZOJ1535: [POI2005]Sza-Template 双向链表+KMP

题解：

确实是一道好题哦。

对于一个前缀，考虑这个前缀所有出现位置的终点，若任意两个相邻的终点之间的差值不超过这个前缀的长度，且$n$也是一个终点，则显然能够满足要求。

我们通过KMP得到Fail树，那么一个前缀的终点位置集合就是所有子树内的点。

那么相当于要求子树内两两相邻权值之间的差值的最大值。

我们找出$n$的祖先那一条链，每往上走一步，集合都会扩大，我们可以利用平衡树求前驱后继以及堆来维护最大差值。

时间复杂度$O(nlogn)$。

但是还有更加优秀的算法：

我们从上往下走，那么只需每次删除集合中的元素，我们利用双向链表维护即可，每删除一个元素$i$就用$r[i]-l[i]$更新答案，由于求的是最大值这样是正确的。

于是就做到了$O(n)$。

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 500010

int head[N],next[N],end[N];
void addedge(int a,int b){
	static int q=1;
	end[q]=b;
	next[q]=head[a];
	head[a]=q++;
}

char s[N];

int fail[N],son[N];
int l[N],r[N];

int mx=1;
void dfs(int x){
	l[r[x]]=l[x];
	r[l[x]]=r[x];
	if(l[x]&&r[x])
		mx=max(r[x]-l[x],mx);
	for(int j=head[x];j;j=next[j])
		dfs(end[j]);
}
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int i,j;
	for(j=0,i=2;i<=n;++i){
		while(j&&s[j+1]!=s[i])
			j=fail[j];
		if(s[j+1]==s[i])
			++j;
		fail[i]=j;
	}
	for(i=1;i<=n;++i)
		addedge(fail[i],i);
	for(i=n;i;i=fail[i])
		son[fail[i]]=i;
	for(i=1;i<=n;++i){
		l[i]=i-1;
		r[i]=i+1;
	}
	l[1]=r[n]=0;
	
	for(i=0;son[i];i=son[i]){
		for(j=head[i];j;j=next[j])
			if(end[j]!=son[i])
				dfs(end[j]);
		if(mx<=son[i]){
			printf("%d",son[i]);
			break;
		}
	}
	
	return 0;
}