NOI 一轮复习：前置知识

我们记字符集为 $\Sigma$ ，字符串是由若干字符集中的元素构成的序列。

字符串哈希

即序列哈希，快速比较两个序列的相等情况。一般来讲我们采用 $b$ 进制方式的哈希，即 $f(s)=\sum_{i=1}^{l}s_i\times b^{l-i}$ 。

1	inline u64 q(u64 f, int l, int r) { return f[r] - f[l - 1] p[r - l + 1]; }

最小表示法

模板，目的是求一个循环同构的字符串的最小字典序。

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

int n;
char a[N];

int getmin(void) {
    int i = 0, j = 1;
    while (i < n && j < n) {
        int k = 0;
        while (k < n && a[(i + k) % n] == a[(j + k) % n]) ++k;
        
        if (a[(i + k) % n] > a[(j + k) % n]) i += k + 1;
        else j += k + 1;

        if (i == j) ++i;
    }
    return min(i, j);
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> a;
    int v = getmin();
    for (int i = 0; i < n; ++i) cout << a[(i + v) % n];
    cout << '\n';
    return 0;
}