POJ 1509 Glass Beads 後綴自動機

POJ 1509 Glass Beads 後綴自動機

題目大意：給出一個環形的字符串，問從哪裡開始是的這個字符串的字典序最小。

思路：最小表示法和後綴自動機的裸題，不過我是為了學後綴自動機才寫的這個題，就沒有去學最小表示法。

做法很簡單，先建立一個後綴自動機，然後從根開始沿tranc指針從a->z走len次到達的點就是字典序最小的字符串的結尾點，求起始點只要減一下長度再+1即可。

對於後綴自動機的理解：www.Bkjia.com

CODE：
 

#include 
#include 
#include 
#include 
#define MAX 10010
using namespace std;

struct Complex{
	Complex *tranc[26],*father;
	short len;
}mempool[MAX << 2],*C = mempool,none,*nil = &none,*root,*last;
Complex *NewComplex(int _)
{
	C->len = _;
	fill(C->tranc,C->tranc + 26,nil);
	C->father = nil;
	return C++;
}

int T;
char s[MAX];

inline void Initialize()
{
	C = mempool;
	root = last = NewComplex(0);
}

inline void Add(int c)
{
	Complex *np = NewComplex(last->len + 1),*p = last;
	for(; p != nil && p->tranc[c] == nil; p = p->father)
		p->tranc[c] = np;
	if(p == nil)	np->father = root;
	else {
		Complex *q = p->tranc[c];
		if(q->len == p->len + 1)	np->father = q;
		else {
			Complex *nq = NewComplex(p->len + 1);
			nq->father = q->father;
			q->father = np->father = nq;
			memcpy(nq->tranc,q->tranc,sizeof(q->tranc));
			for(; p != nil && p->tranc[c] == q; p = p->father)
				p->tranc[c] = nq;
		}
	}
	last = np;
}

int main()
{
	for(cin >> T; T--;) {
		Initialize();
		scanf(%s,s);
		int length = strlen(s);
		for(int i = 0; i < length; ++i)
			Add(s[i] - 'a');
		for(int i = 0; i < length; ++i)
			Add(s[i] - 'a');
		Complex *now = root;
		for(int i = 0; i < length; ++i)
			for(int j = 0; j < 26; ++j)
				if(now->tranc[j] != nil) {
					now = now->tranc[j];
					break;
				}
		printf(%d
,now->len - length + 1);
	}
}