编织幻梦

看一次忘一次，蛋疼死了。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
const int char_size=26;
const int pool_size=100000;
class suffixs_automaton
{
public:
	struct suffix_node{
		bool start;
		int length;
		suffix_node * clean(){
			return this;
		}
		suffix_node*ch[char_size];
		suffix_node*f;
		suffix_node(){
			start=false;
			length=0;
			f=NULL;memset(ch,0,sizeof(ch));
		};
	};
private:
	// 私有变量
	suffix_node suffix_node_pool[pool_size+1];
	int poolsize;
	suffix_node*alloca_node(){ if (poolsize==pool_size) {suffix_node *sn = new suffix_node();assert(sn);}return suffix_node_pool[poolsize++].clean();};
	suffix_node*tail;
	suffix_node*start;
	int length;
public:
	suffixs_automaton(int *c,int len); // [0,len)
	const suffix_node * get_start();
	void add(int c);
private:
	// 内部函数
};
suffixs_automaton::suffixs_automaton(int *c,int len){
	poolsize = 0;
	start = tail = alloca_node();
	start->start=true;length=0;
	for (int i=0;i<len;i++) add(c[i]);
};
const suffixs_automaton::suffix_node * suffixs_automaton::get_start(){
	return start;
};
void suffixs_automaton::add(int c){
	length++;suffix_node*p=tail;suffix_node*np=alloca_node();
	np->length = tail->length+1;
	for (;!!p && !p->ch[c];p=p->f) p->ch[c]=np;
	tail = np;
	if (!p) {np->f=start;return ;}
	if (p->ch[c]->length==p->length+1) np->f=p->ch[c];
	else
	{
		suffix_node*r = alloca_node();suffix_node *q=p->ch[c];
		*r=*q;
		r->length = p->length+1;
		q->f=np->f=r;
		for (;p&&p->ch[c]==q;p=p->f) p->ch[c]=r;
	}
};
int p[]={0,2,0,3,3};
suffixs_automaton SA(p,5);
char c[255];
void dfs(const suffixs_automaton::suffix_node *sn,int l){
	assert(sn);
	if (l!=0) printf("%s\n",c);
	for (int i=0;i<5;i++)
		if (sn->ch[i]){
			c[l]='A'+i;
			dfs(sn->ch[i],l+1);
			c[l]=0;
		}
}
int main(){
	const suffixs_automaton::suffix_node *sn = SA.get_start();
	dfs(sn,0);
	system("pause");
};