題目大意：給出一個環(huán)形的字符串，問從哪里開始是的這個字符串的字典序最小，

POJ 1509 Glass Beads 后綴自動機

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

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

    對于后綴自動機的理解：www.2cto.com

    CODE：

#include<cstdio>#include<cstring>#include<iostream>#include #define MAX 10010using 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);	}}</iostream></cstring></cstdio>