Note: This article is available in Chinese only. 本文暂无英文版本。
View original
首先放一波资料：
参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。
一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。
令i=0,j=1 如果S[i] > S[j] i=j, j=i+1 如果S[i] < S[j] j++ 如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j] _ __如果S[i+k] > S[j+k] i=j,j=i+1 _ 否则j++ 返回i
注意到，朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。
令i=0,j=1 如果S[i] > S[j] i=j, j=i+1 如果S[i] < S[j] j++ 如果S[i]==S[j] 设指针k，分别从i和j位置向下比较，直到S[i] != S[j] **如果S[i+k] > S[j+k] i=i+k ** 否则j++ 返回i和j的小者
注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。 值得一提的是，与KMP类似，最小表示法处理的是一个字符串S的性质，而不是看论文时给人感觉的处理两个字符串。 应用最小表示法判断两个字符串同构，只要将两个串的最小表示求出来，然后从最小表示开始比较。剩下的工作就不用多说了。
模板：
1#include <stdio.h>
2#include <string.h>
3const int N = 100000+10;
4char str[N];
5int minimalRepresentation()
6{
7 int n = strlen(str);
8 int i = 0,j = 1, k = 0;
9 while(i<n && j<n && k<n)
10 {
11 int t = str[(i+k)%n] - str[(j+k)%n] ;
12 if(t == 0)
13 k++;
14 else
15 {
16 if(t>0)
17 i+=k+1;
18 else
19 j+=k+1;
20 if(i==j)
21 j++;
22 k = 0;
23 }
24 }
25 return i < j ? i : j;
26}
27int main()
28{
29 int t;
30 scanf("%d",&t);
31 int n;
32 while(t--)
33 {
34 scanf("%d",&n);
35 scanf("%s",str);
36 int index = minimalRepresentation();
37 printf("%d\n",index);
38 }
39}