题解：P1709 [USACO5.5] 隐藏口令 Hidden Password
Problem Link
[USACO5.5] 隐藏口令 Hidden Password
题目描述
求最小表示法的开头字母在原字符串的位置。
Solution
最小表示法板子，双指针解决即可。
Code
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
#define Maxn 10000005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
void train() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}
int n, l = 1, r = 2;
char s[Maxn];
int main()
{
train();
cin >> n;
fo(i, 1, n) cin >> s[i], s[i+n] = s[i];
int cnt = 0;
while(l <= n && r <= n)
{
cnt = 0;
while(cnt < n && s[l+cnt] == s[r+cnt]) ++cnt;
if(cnt == n) break;
if(s[l+cnt] > s[r+cnt]) {l += cnt+1; if(l == r) ++l;}
else {r += cnt+1; if(l == r) ++r;}
}
printf("%d", min(l, r)-1);
return 0;
}