字符串 最小表示法

定义：

表示：
若对于一个字符串 (S) ，和另一个字符串 (S^prime)
若存在一个 (i) 使得 (S^prime[i...N]S^prime[1...i-1]) 与 (S) 相等，那么就说 (S^prime) 是 (S) 的一个表示（也称 (S^prime) 与 (S) 循环同构）。
(S) 的最小表示就是满足上述条件的字典序最小的 (S^prime)

---

算法复杂度

我们还是先来看看暴力的复杂度：
(O(n^2))
枚举最小表示的开头，暴力判断是否循环同构。
这种做法的时间主要消耗在比较上，如果是随机数据，则表现良好，但是如果是这种：

[aaaa...aaa ]

每次比较次数将达到 (O(n)) 级别，整个算法就成了 (O(n^2))
而我们接下来的算法复杂度是妥妥的 (O(n))

---

合理解法

我们考虑两个字符串 (A,B)，它们在 (S) 中的起始位置分别为 (i,j) ，且它们的前 (k) 位都相等。
如果 (A[i+k]>B[j+k]) 那么对于任何一个字符串 (T) ，它的开头位于 (i) 和 (i+k) 之间，那么它肯定不会成为最优解（想一想为什么）。
所以我们就可以直接将 (i) 跳至 (i+k+1)。
复杂度证明：不会。。。

---

模板题

Luogu
代码：

/*--------------------------------
--Author: The Ace Bee-------------
--Blog: www.cnblogs.com/zsbzsb----
--This code is made by The Ace Bee
--------------------------------*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <string>
#define rg register
#define clr(x, y) memset(x, y, sizeof x)
using namespace std;
template < typename T > inline void read(T& s) {
	s = 0; int f = 0; char c = getchar();
	while (!isdigit(c)) f |= (c == '-'), c = getchar();
	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
	s = f ? -s : s;
}

const int _ = 30010;

int n, L; char s[_], t[_];

inline void solve() {
	scanf("%s", s), L = strlen(s);
	int k = 0, i = 0, j = 1;
	while (k < L && i < L && j < L) {
		int tmp = s[(i + k) % L] - s[(j + k) % L];
		if (tmp == 0) ++k;
		else {
			if (tmp < 0) j += k + 1;
			if (tmp > 0) i += k + 1;
			if (i == j) ++i; k = 0;
		}
	}
	printf("%d
", min(i, j) + 1);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
#endif
	read(n);
	for (rg int i = 1; i <= n; ++i) solve();
	return 0;
}