题目大意：给出一个环形的字符串，问从哪里开始是的这个字符串的字典序最小，
POJ 1509 Glass Beads 后缀自动机
。思路：最小表示法和后缀自动机的裸题，不过我是为了学后缀自动机才写的这个题，就没有去学最小表示法。
做法很简单，先建立一个后缀自动机，然后从根开始沿tranc指针从a->z走len次到达的点就是字典序最小的字符串的结尾点，求起始点只要减一下长度再+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>