●SPOJ 8222 NSUBSTR–Substrings

题链：

http://www.spoj.com/problems/NSUBSTR/
题解：

后缀自动机。
不难发现，对于自动机里面的一个状态s,
如果其允许的最大长度为maxs[s],其right集合的大小为right[s]，
那么显然就可能对ANS[maxs[s]]造成贡献,即ANS[maxs[s]]=max(ANS[maxs[s]],right[s])
最后再反向扫一遍ANS数组，从后向前取max即可。
那么现在的问题就是如何求得right[]数组，即如何求出每个状态的right集合的大小。
根据构造过程，首先给“主链”上的状态的right[]赋值为1,
然后可以发现，虽然parent树并不好直接遍历，但是由于父亲状态的maxs一定小于儿子状态的maxs，
所以使用桶排序对所有状态按maxs从大到小排序后，依次遍历每个状态，去给其父亲贡献即可求得right[]数组。
整个过程是O(N)的。

代码：

#include<bits/stdc++.h>

#define MAXN 250005

using namespace std;

int ANS[MAXN];

struct SAM{

	int size,last;

	int maxs[MAXN*3],trans[MAXN*3][26],parent[MAXN*3],right[MAXN*3];

	int Newnode(int a,int b){

		++size; maxs[size]=a;

		memcpy(trans[size],trans[b],sizeof(trans[b]));

		return size;

	}

	void Extend(int x){

		static int p,np,q,nq;

		p=last; last=np=Newnode(maxs[p]+1,0);

		for(;p&&!trans[p][x];p=parent[p]) trans[p][x]=np;

		if(!p) parent[np]=1;

		else{

			q=trans[p][x];

			if(maxs[p]+1!=maxs[q]){

				nq=Newnode(maxs[p]+1,q);

				parent[nq]=parent[q];

				parent[q]=parent[np]=nq;

				for(;p&&trans[p][x]==q;p=parent[p]) trans[p][x]=nq;

			}

			else parent[np]=q;

		}

	}

	void Build(char *S){

		memset(trans[0],0,sizeof(trans[0]));

		size=0; last=Newnode(0,0);

		for(int i=0;S[i];i++) Extend(S[i]-'a');

	}

	void Count_Right(char *S,int len){

		static int p=1,tmp[MAXN],order[MAXN*3];

		for(int i=0;S[i];i++) p=trans[p][S[i]-'a'],right[p]=1;

		for(int i=1;i<=size;i++) tmp[maxs[i]]++;

		for(int i=1;i<=len;i++) tmp[i]+=tmp[i-1];

		for(int i=size;i;i--) order[tmp[maxs[i]]--]=i;

		for(int i=size;i;i--)

			p=order[i],right[parent[p]]+=right[p];

	}

}SUF;

int main(){

	char S[MAXN]; int len;

	scanf("%s",S); len=strlen(S);

	SUF.Build(S);

	SUF.Count_Right(S,len);

	for(int i=1;i<=SUF.size;i++)

		ANS[SUF.maxs[i]]=max(ANS[SUF.maxs[i]],SUF.right[i]);

	for(int i=len;i;i--) ANS[i]=max(ANS[i],ANS[i+1]);

	for(int i=1;i<=len;i++) printf("%d\n",ANS[i]);

	return 0;

}