[USACO 5.5]Hidden Password

Description

题库链接

给你一个长度为 $n$ 的字符串环，求从哪个位置断开所得的字符串字典序最小。

$1\leq n\leq 5000000$

Solution

康复训练 $\times 1$。

字符串的最小表示法。具体操作可以参考洛谷题解第一篇。

这里解释一下为什么题解中的i要移动到i+k+1而不是i++。

我们记 $S_{l,r}$ 表示字符串 $S$ 从第 $l$ 位到 $r$ 位的字串。

由题 $S_{i,i+k-1}=S_{j,j+k-1}$。因为 $S_{i+k}>S_{j+k}$，故对于任意的 $0\sim k-1$ 之间的数 $x$，都会存在 $S_{i+x,i+k}>S_{j+x,j+k}$ 。

即跳过的部分都不是最优，故可行。

时间复杂度为 $O(2n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5000000+5;

char ch[N];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i <= n; i += 72)
        scanf("%s", ch+i);
    int i, j, k, t;
    for (i = 0, j = 1, k = 0; i < n && j < n && k < n; ) {
        t = ch[(i+k)%n]-ch[(j+k)%n];
        if (t == 0) ++k;
        else {
            if (t < 0) j += k+1;
            else swap(i, j), j += k+1;
            if (i == j) ++j;
            k = 0;
        }
    }
    printf("%d\n", i);
    return 0;   
}