最小表示法

---

【用途】： 求解某字符串$S$S的最小循环同构字符串的首字符在$S$S中的位置。

---

【算法剖析】：

     最小表示法是暴力求解的优化，利用双指针的交替移动实现。
     假设$S[i到i+k-1]=S[j到j+k-1]$S[i到i+k−1]=S[j到j+k−1],此时应该同步匹对下一位下一位如果不相等那么这两个字符串一定会分出大小，若$S[i+k]&gt;S[j+k]$S[i+k]>S[j+k]，这意味着$j$j开头的串更小，而且我们可以得出，在$i到i+k$i到i+k之间的开头的字符串在$j到j+k$j到j+k中一定可以找到一个更优的点作为开头。所以$i到i+k$i到i+k之间没有必要再枚举了$i+=k+1$i+=k+1。当$S[i+k]&lt;S[j+k]$S[i+k]<S[j+k]时同理。
     双指针在交替后退时，一旦哪一个指针扫到了目标位置，该指针便会被固定，另一个指针可能会一直被淘汰到末尾，也可能存在多解，使$k$k饱和。

---

【模板题】： POJ 1509 Glass Beads

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 1;
typedef  long long ll;
int T;
char s[N];
int Min(char* s)
{
	int i = 0;
	int j = 1;
	int k = 0;
	int match_i, match_j;
	int n = strlen(s);
	while(i < n && j < n && k < n)
	{
		 match_i = (i + k) % n;
		 match_j = (j + k) % n;
		 if(s[match_i] == s[match_j]) k++;
		 else
		 {
			 if(s[match_i] > s[match_j])
				 i += k + 1;
			 else 
				 j += k + 1;
			 if(i == j) j++;
			 k = 0;
		 }	
	}
	return min(i, j) + 1;
}
int main()
{		
	scanf("%d", &T);getchar();
	while(T--)
	{
		scanf("%s", s);getchar();
		int ans = Min(s);
		printf("%d\n", ans);
	}
	return 0;
}    

---