Hidden Password

zoj1729:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=729

题意：就是求字符串的最小表示，模板题。

题解：直接贴模板。

最小表示的学习：http://www.cnblogs.com/ACAC/archive/2010/05/23/1742349.html

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n;
 7 char str[100002];
 8 int MinimumRepresentation(char *s,int l)//串s[0~l-1]的最小表示位置
 9 {
10     int i = 0, j = 1, k = 0,t;
11     while (i < l && j < l && k < l)//找不到比它还小的 或者 完全匹配
12     {
13         t = s[(i+k)%l] - s[(j+k)%l];
14         if (t == 0)
15             k++;//相等的话,检测长度加1
16         else{
17             if (t > 0)//大于的话,s[i]为首的肯定不是最小表示,最大表示就改<
18                 i += k + 1;
19             else
20                 j += k + 1;
21             if (i==j)
22                 j++;
23             k = 0;
24         }
25     }
26     return min(i,j);
27 }
28 int main(){
29    int cas;
30    scanf("%d",&cas);
31    while(cas--){
32       memset(str,0,sizeof(str));
33       scanf("%d %s",&n,str);
34       printf("%d
",MinimumRepresentation(str,n));
35    }
36 }

View Code