记录编号	296583	评测结果	AAAAAAAAAA
题目名称	1709.[SPOJ 705] 不同的子串	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-08-15 18:46:38	内存使用	10.97 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int cnt = 0;
const int MAXN = 5e4+20;
class SAM
{
	int size, last;
	public:
	struct state
	{
		int len, link;
		int next[26];
		void init()
		{
			len = 0;
			link = -1;
			memset(next, 0, sizeof(next));
		}
	}st[MAXN<<1];
	SAM()
	{
		last = size = 0;
		newst();
	}
	int newst()
	{
		st[size++].init();
		return size-1;
	}
	void expand(int c)
	{
		int cur = newst();
		st[cur].len = st[last].len + 1;
		int p;
		for(p = last; p != -1 && !st[p].next[c]; p = st[p].link)
			st[p].next[c] = cur;
		if(p == -1)
		{
			st[cur].link = 0;
		}else
		{
			int q = st[p].next[c];
			if(st[q].len == st[p].len + 1)
				st[cur].link = q;
			else
			{
				int clone = newst();
				st[clone].len = st[p].len + 1;
				st[clone].link = st[q].link;
				memcpy(st[clone].next, st[q].next, 26*sizeof(int));
				for(; p != -1 && st[p].next[c] == q; p = st[p].link)
					st[p].next[c] = clone;
				st[cur].link = st[q].link = clone;
			}
		}
		cnt += st[cur].len - st[st[cur].link].len;
		last = cur;
	}
};
SAM s;
int main()
{
	freopen("subst1.in", "r", stdin);
	freopen("subst1.out", "w", stdout);
	char c;
	while(c = getchar())
		if(c >= 'A' && c <= 'Z')
			break;
    s.expand(c - 'A');
	while(c = getchar())
	{
		if(c >= 'A' && c <= 'Z')
			s.expand(c - 'A');
		else
		{
			printf("%d\n", cnt);
			break;
		}
	}
	return 0;
}