Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月12日 星期五 18时48分29秒
4File Name :code/uva/1314.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n ;
35char s[N];
36int minRep(char *s)
37{
38 int n = strlen(s);
39 int i = 0;
40 int j = 1;
41 int k = 0;
42 while (i<n&&j<n&&k<n)
43 {
44 int t = s[(i+k)%n]-s[(j+k)%n];
45 if (t==0) k++;
46 else
47 {
48 if (t>0)
49 i+=k+1;
50 else j+=k+1;
51 if (i==j) j++;
52 k = 0 ;
53 }
54 }
55 return i<j?i:j;
56}
57int main()
58{
59 #ifndef ONLINE_JUDGE
60 freopen("code/in.txt","r",stdin);
61 #endif
62 int T;
63 cin>>T;
64 while (T--)
65 {
66 scanf("%d\n%s",&n,s);
67 printf("%d\n",minRep(s));
68 }
69 #ifndef ONLINE_JUDGE
70 fclose(stdin);
71 #endif
72 return 0;
73}