【SPOJ8222】Substrings

  对SAM的理解还不够深刻。仅仅是敲完了AC代码，但还有几个问题没有搞清楚。

  大概就是建完SAM后构造拓扑序，按照拓扑序更新信息。

  如果一个状态v对应的最长后缀的数量为c，那么状态v的link状态对应的最长后缀数量应该也加上c，因为v的link状态对应最长后缀是v状态对应最长后缀的后缀。

  后来仔细看了一下文章，基本上是搞懂了这个过程。

  一个状态有一个结束位置集合endpos，意即从初始状态走到该状态得到的所有子串在原串中结束位置的集合都是endpos。显然endpos中的元素个数也就是这些子串在原串中出现次数。

  一个状态对应一个不同于其他任何状态的结束位置集合endpos，一个状态的link状态的endpos一定包含该状态的endpos（除了初始状态）。

  在构造SAM时，代表原串中第i个字符的状态只有一个结束位置{i}，用这个去更新他们的link状态的值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500010;

struct SAM
{
	struct State
	{
		int next[26];
		int link;
		int len;
	}st[maxn];

	int last,cnt;
	int ccnt[maxn];
	int temp[maxn];
	int sum[maxn];

	SAM() {last=cnt=1;st[1].link=0;st[1].len=0;}

	void Extend(int c)
	{
		int x=++cnt,p;
		st[x].len=st[last].len+1;
		for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
		if (!p) st[x].link=1;
		else {
			int q=st[p].next[c];
			if (st[p].len+1==st[q].len) st[x].link=q;
			else {
				int v=++cnt;
				st[v].len=st[p].len+1;
				memcpy(st[v].next,st[q].next,sizeof(st[v].next));
				st[v].link=st[q].link;
				for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
				st[q].link=st[x].link=v;
			}
		}
		last=x;
	}

	void Query(int n,int *f,char *ch)
	{
		for (int i=0,p=1;i<n;i++) sum[(p=st[p].next[ch[i]-'a'])]=1;
		for (int i=1;i<=cnt;i++) ccnt[st[i].len]++;
		for (int i=1;i<=n;i++) ccnt[i]+=ccnt[i-1];
		for (int i=1;i<=cnt;i++) temp[ccnt[st[i].len]--]=i;
		for (int i=cnt;i;i--)
		{
			int x=temp[i];
			f[st[x].len]=max(f[st[x].len],sum[x]);
			sum[st[x].link]+=sum[x];
		}
		for (int i=n-1;i;i--) f[i]=max(f[i],f[i+1]);
	}
}M;

char ch[maxn];
int f[maxn];
int n;

int main()
{
	scanf("%s",ch);
	n=strlen(ch);
	for (int i=0;i<n;i++) M.Extend(ch[i]-'a');
	M.Query(n,f,ch);
	for (int i=1;i<=n;i++) printf("%d\n",f[i]);
	return 0;
}