Uva 1584 基操之O(n)时间求出最小循环字符串

紫薯P52 例题3-6

一、题意

有kase个循环字符串，输出每个字符串 (长度n<=100) 的最小表示。

二、解析

经典的求最小循环字符串题目，这里用来复习一下它的一种O(1)算法。

基本思想是双指针i, j，用k表示从i、j开始的子串的当前比对到的完全一样的长度，当判断出i、j的某一条子串的i+k、j+k位置有所不同时，大的那一条（比如是j）就可以往后跳k+1个字符，因为以这些字符起始的循环字符串已经不可能是最小的（比它们小的在i开始的串的子串中）。用这样的方法当i、j串中的某一个超过n时就不用再判断了（因为n个可能的起始位置都判断过了）。此时剩余的那个串就是最小的循环字符串。

三、代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int kase, n;
string str;

int solve() {
    int i = 0, j = 1, k = 0;
    while(i < n && j < n) {
        int tmp = str[(i + k) % n] - str[(j + k) % n];
        if(tmp == 0) k ++;
        else if(tmp < 0) j += k + 1, k = 0;
        else i += k + 1, k = 0;
        if(i == j) j ++, k = 0;
    }
    return min(i, j);
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> str;
        n = str.size();
        int idx = solve();
        cout << str.substr(idx) + str.substr(0, idx) << endl;
    }
}

/*
2
CGAGTCAGCT
CTCC
*/

四、归纳

• 经典算法可以记一下：O(1)时间求最小循环字符串。

差点写不出来...