Author: lllyouo
Date: 20250917
tag: 字符串、最小表示法
link: https://www.luogu.com.cn/problem/P13270

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int min_rep(string s) {
    int n = s.size(), i = 0, j = 1, k = 0;

    while (k < n && i < n && j < 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 j = j + k + 1;

            k = 0;
            if (i == j) i++;
        }
    }

    return min(i, j);
}

int main() {
    cin >> n;
    cin >> s;

    int t = min_rep(s);
    for (int i = t; i < n; i++) cout << s[i];
    for (int i = 0; i < t; i++) cout << s[i];

    return 0;
}