在这里插入图片描述
UVA719
将循环串$S$展开成两倍大小：$S+S$，这样线性处理就可以处理所有循环的情况了。对$S+S$建立一个后缀自动机，让后从初始状态开始走，每次选择字典序最小的道路，走$N$步就得到一个字典序最小的原串了。假设最后走到$p$，那么此时首字符下标即为$len(p)-N+1$，即从首字符的位置走了$N$步到$p$。
AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
const int MAXN = 20000;
int n;
char S[2*MAXN], Buffer[MAXN];
struct SAM {
	int size, last;
	struct Node {
		int len, link;
		int next[26];
		int cnt;
		void clear() {
			len = link = 0;
			memset(next, 0, sizeof(next));
		}
	} node[MAXN * 2];
	void init() {
		for (int i = 0; i < size; i++) {
			node[i].clear();
		}
		node[0].link = -1;
		size = 1;
		last = 0;
	}
	void insert(char x) {
		int ch = x - 'a';
		int cur = size++;
		node[cur].len = node[last].len + 1;
		node[cur].cnt = 1;
		int p = last;
		while (p != -1 && !node[p].next[ch]) {
			node[p].next[ch] = cur;
			p = node[p].link;
		}
		if (p == -1) {
			node[cur].link = 0;
		}
		else {
			int q = node[p].next[ch];
			if (node[p].len + 1 == node[q].len) {
				node[cur].link = q;
			}
			else {
				int clone = size++;
				node[clone] = node[q];
				node[clone].len = node[p].len + 1;
				node[clone].cnt = 0;
				while (p != -1 && node[p].next[ch] == q) {
					node[p].next[ch] = clone;
					p = node[p].link;
				}
				node[q].link = node[cur].link = clone;
			}
		}
		last = cur;
	}
} sam;
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		sam.init();
		scanf("%s", S);
		n = strlen(S);
		strcpy(Buffer, S);
		strcat(S, Buffer);
		n = strlen(S);
		for (int i = 0; i < n; i++) {
			sam.insert(S[i]);
		}
		int&& Cur = 0;
		n /= 2;
		//走N步
		for (int i = 0; i < n ; ++i) {
			for (int j = 0; j < 26; ++j) {
				//如果走得通（走最小的）
				if (sam.node[Cur].next[j]) {
					Cur = sam.node[Cur].next[j];
					break;
				}
			}
		}
		printf("%d\n", sam.node[Cur].len - n + 1);
	}
	return 0;
}