后缀自动机模板

@(学习笔记)[后缀自动机]
不想写了.
贴一份代码吧.

#include <cstdio>
#include <cstring>

struct suffixAutomaton
{
	const int ORG = 'A';
	
	struct state
	{
		int stp;
		state *pre, *suc[1 << 5];

		inline state(int _stp = 0)
		{
			stp = _stp;
			pre = NULL;
			memset(suc, NULL, sizeof(suc));
		}
	};

	state *lst, *s;

	inline void add(int c)
	{
		state *u = new state(lst->stp + 1), *p = lst;

		for(; p != NULL && p->suc[c] == NULL; p = p->pre)
			p->suc[c] = u;

		if(p == NULL)
			u->pre = s;
		else
		{
			state *q = p->suc[c];

			if(p->stp + 1 == q->stp)
				u->pre = q;
			else
			{
				state *v = new state(p->stp + 1);
				memcpy(v->suc, q->suc, sizeof(q->suc));
				v->pre = q->pre;
				q->pre = u->pre = v;

				for(; p != NULL && p->suc[c] == q; p = p->pre)
					p->suc[c] = v;
			}
		}
		
		lst = u;
	}

	inline void build(char *str, int len)
	{
		lst = s = new state;

		for(int i = 0; i < len; ++ i)
			add(str[i] - ORG);
	}

	char str[1 << 5];

	inline void dfs(state *u, int len)
	{
		for(int i = 0; i < 26; ++ i)
			if(u->suc[i] != NULL)
			{
				str[len ++] = i + ORG;
				
				for(int i = 0; i < len; ++ i)
					putchar(str[i]);
				
				putchar('
');
				
				dfs(u->suc[i], len);
				-- len;
			}
	}

	inline void getOutput()
	{
		memset(str, 0, sizeof(str));
		dfs(s, 0);
	}
}sam;

int main()
{
	freopen("sam.in", "r", stdin);
	freopen("sam.out", "w", stdout);

	char s[1 << 5];
	scanf("%s", s);
	
	sam.build(s, strlen(s));
	sam.getOutput();
}