[USACO5.5]隐藏口令Hidden Password [最小表示法模板]

最小表示法就是一个字符串构成一个环，找以哪个点为开头字典序最小。

然后我们就可以用n²的算法愉快的做啦~实际上有O(n)的做法的，就是用两个指针扫，如果这两个位置的字典序相等，就一起往后，如果某一个大，就把那个指针指到大的那个的后面。

每次至少有一个指针往后移一个，复杂度就是线性的了。

（自己YY的，求不出锅）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char s[5000005];
int main() {
    scanf("%d",&n);
    char c;
    for(int i=0;i<n;i++) scanf(" %c",&c),s[i]=c;
    int i=0,j=1,k=0;
    while(i<n&&j<n&&k<n) {
        s[(i+k)%n]-s[(j+k)%n];
        if(s[(i+k)%n]==s[(j+k)%n]) k++;
        else {
            if(s[(i+k)%n]>s[(j+k)%n]) i=i+k+1;
            else if(s[(i+k)%n]<s[(j+k)%n]) j=j+k+1;
            if(i==j) j++;
            k=0;
        }
    }
    printf("%d
",min(i,j));
}