poj 1509 Glass Beads (后缀自动机求最小循环表示)
题意：
给定一个循环字符串，问字典序最小的串的开始位置。
思路：
之前用poj 1509 解题报告-字符串的最小表示法 A过
字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。
参照张天扬的论文：
把原串复制一遍到后面，然后构建后缀自动机。从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。
如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月03日 星期五 18时20分42秒
4File Name :2774_SAM.cpp
5************************************************ */
6
7//#include <bits/stdc++.h>
8#include <iostream>
9#include <cstdio>
10#include <algorithm>
11#include <cmath>
12#include <string>
13#include <cstring>
14#define PB push_back
15#define fst first
16#define sec second
17#define lnxt l,m,rt<<1
18#define rnxt m+1,r,rt<<1|1
19#define ms(a,x) memset(a,x,sizeof(a))
20typedef long long LL;
21#define pi pair < int ,int >
22#define MP make_pair
23
24using namespace std;
25const double eps = 1E-8;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28const int inf = 0x3f3f3f3f;
29
30const int maxn = 5E5;
31
32struct node{
33 node*nxt[26],*fail;
34 LL len,cnt;
35};
36struct SAM{
37 node no[maxn];
38 node*root;
39 int cnt;
40 node*newnode(){
41 ms(no[cnt].nxt,0);
42 no[cnt].fail=NULL;
43 no[cnt].len = no[cnt].cnt = 0;
44 return &no[cnt++];
45 }
46 void init()
47 {
48 cnt = 0;
49 root = newnode();
50 }
51 SAM(){
52 cnt = 0;
53 root = newnode();
54 }
55 node*add(int c,node*p){
56 node*cur = newnode();
57 cur->len = p->len+1;
58 while(p&&!p->nxt[c]){
59 p->nxt[c] = cur;
60 p = p->fail;
61 }
62 if(!p){
63 cur->fail = root;
64 return cur;
65 }
66 node*q = p->nxt[c];
67 if(p->len+1==q->len){
68 cur->fail = q;
69 }else{
70 node*nq = newnode();
71 *nq = *q;
72 q->fail = cur->fail = nq;
73 nq->len = p->len+1;
74 while(p&&p->nxt[c]==q){
75 p->nxt[c] = nq;
76 p = p->fail;
77 }
78 }
79 return cur;
80 }
81 int calc(int L)
82 {
83 node *p =root;
84 for ( int i = 0 ; i < L ; i++)
85 {
86 bool flag = false;
87 for ( int j = 0 ; j < 26 ; j++) //找字典序最小的.
88 if (p->nxt[j])
89 {
90 flag = true;
91 p=p->nxt[j];
92 break;
93 }
94 if (!flag) break;
95 }
96 return p->len + 1 - L;
97 }
98};
99SAM sam;
100string A,B;
101int main()
102{
103 #ifndef ONLINE_JUDGE
104 freopen("./in.txt","r",stdin);
105 #endif
106 int T;
107 cin>>T;
108 while (T--)
109 {
110 sam.init();
111 node *cur =sam.root;
112 cin>>A;
113 for ( int i = 0 ; i < A.length() ; i++https://111qqz.com/wordpress/wp-admin/post-new.php#) cur = sam.add(A[i]-'a',cur);
114 for ( int i = 0 ; i < A.length() ; i++) cur = sam.add(A[i]-'a',cur);
115 int ans = sam.calc(A.length());
116 printf("%d\n",ans);
117 }
118
119 #ifndef ONLINE_JUDGE
120 fclose(stdin);
121 #endif
122 return 0;
123}