bzoj-1535 Sza-Template

題意：

給出一個長度為n的字元串，求用它的一個子串作為模闆能粘貼出整個字元串的最小長度；

n<=500000；

題解：

首先我們可以知道，這個模闆串一定是既為原串的一個字首也為它的一個字尾的，否則并不能拼出來這個字元串

那麼利用KMP或AC自動機建構出fail樹，答案隻可能出現在樹中(root,n]這條路徑上；

那麼問題就是：枚舉樹上的每一個點(也是串中的一個字首)，判斷它是否能覆寫整個字元串，能的話更新答案；

這步轉化之後複雜度沒有改變，但是fail樹上還有另一個性質：一個點代表的字元串是這個點的子樹中所有點的字尾，且擁有這個字尾的所有串都在子樹内；

是以我們隻要維護這個子樹中相鄰兩個比對點的最大間隔，判斷與原串的大小關系就可以了；

從根向下枚舉，利用子樹集合單調性，用一個連結清單維護子樹元素即可；

每個元素隻會被删除一次，是以總複雜度是O(n)的；

%%%JCVB

順便我又忘了KMP咋寫了啊啊啊

代碼：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 510000
using namespace std;
char str[N];
int fail[N];
int next[N],to[N],head[N],ce;
int son[N],L[N],R[N];
void getfail(int n)
{
	int i=1,j=0;
	fail[1]=0;
	while(i<=n)
	{
		if(j==0||str[i]==str[j])
		{
			i++,j++;
			fail[i]=j;
		}
		else
			j=fail[j];
	}
}
void add(int x,int y)
{
	to[++ce]=y;
	next[ce]=head[x];
	head[x]=ce;
}
void dfs(int x,int &len)
{
	R[L[x]]=R[x];
	L[R[x]]=L[x];
	len=max(R[x]-L[x],len);
	L[x]=0x3f3f3f3f;
	for(int i=head[x];i;i=next[i])
		dfs(to[i],len);
}
int main()
{
	int n,m,i,j,k,ans,len;
	scanf("%s",str+1);
	n=strlen(str+1);
	getfail(n);
	for(i=1;i<=n;i++)
		fail[i]=fail[i+1]-1,add(fail[i],i);
	i=n;
	while(fail[i])
	{
		son[fail[i]]=i;
		i=fail[i];
	}
	son[0]=i;
	for(i=1;i<=n;i++)
	{
		L[i]=i-1;
		R[i]=i+1;
	}
	for(i=0,ans=n,len=1;i!=n;)
	{
		for(j=head[i];j;j=next[j])
		{
			if(to[j]!=son[i])
			{
				dfs(to[j],len);
			}
		}
		i=son[i];
		if(len<=i)
			ans=min(ans,i);
	}
	printf("%d\n",ans);
	return 0;
}