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;
}