SPOJ NSUBSTR Substrings ——后缀自动机

建后缀自动机

然后统计次数，只需要算出right集合的大小即可，

然后更新f[l[i]]和rit[i]取个max

然后根据rit集合短的一定包含长的的性质，从后往前更新一遍即可

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define maxn 500005

struct sam{

	char s[maxn];

	int len;

	int last,cnt,f[maxn];

	int h[maxn],to[maxn],ne[maxn],en,rit[maxn];

	int go[maxn][26],l[maxn],fa[maxn];

	void init()

	{

		last=cnt=1;

		memset(go,0,sizeof go);

		memset(h,-1,sizeof h);

		en=0;

	}

	void addedge(int a,int b)

	{to[en]=b;ne[en]=h[a];h[a]=en++;}

	void add(int x)

	{

//		printf("add %d\n",x);

		int p=last,np=last=++cnt;l[np]=l[p]+1;rit[np]=1;

		for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;

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

		else

		{

			int q=go[p][x];

			if (l[q]==l[p]+1) fa[np]=q;

			else

			{

				int nq=++cnt;l[nq]=l[p]+1;

				memcpy(go[nq],go[q],sizeof go[q]);

				fa[nq]=fa[q];

				fa[q]=fa[np]=nq;

				for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;

			}

		}

	}

	void dfs(int o)

	{

		for (int i=h[o];i>=0;i=ne[i])

		{

			dfs(to[i]);

			rit[o]+=rit[to[i]];

		}

		f[l[o]]=max(f[l[o]],rit[o]);

	}

	void solve()

	{

		scanf("%s",s+1);

//		printf("%s\n",s+1);

		len=strlen(s+1);

//		printf("len is %d\n",len);

		F(i,1,len) add(s[i]-'a');

		F(i,1,cnt) addedge(fa[i],i);

		dfs(1);

		D(i,len,1) f[i]=max(f[i+1],f[i]);

		F(i,1,len) printf("%d\n",f[i]);

	}

}SAM;

int main()

{

	SAM.init();

	SAM.solve();

}