最小表示法

求出一个字符串的所有循环同构串中字典序最小的一个
主要思想：
先确定两个起始点i、j，向后枚举并比对，如果i串>j串，j=i+1，因为可以证明j～i-1之间不可能有更优解，最后返回i，j的较小值，算法总复杂度为O((2*)n)
详见，进阶指南P73-75

代码

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

int n,len;
char s[1000005];

void solve(){
    len=strlen(s+1);
    for (int i=1;i<=len-1;++i) s[i+len]=s[i];
    int i=1,j=2;
    while (i<=len && j<=len){
        int k=0;
        while (k<len && s[i+k]==s[j+k]) k++;
        if (k==len) break;  //字符串仅由一种字符组成，eg：”aaaaa“
        if (s[i+k]>s[j+k]){
            i=i+k+1;
            if (i==j) i++;
        }else{
            j=j+k+1;
            if (i==j) j++;
        }
    }
    printf("%d\n",min(i,j));
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        scanf("%s",s+1);
        solve();
    }
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/76/