最小表示法的概念

最小表示法是一种用于处理字符串循环同构问题的算法。当一个字符串可以通过循环移位得到另一个字符串时，这两个字符串被称为循环同构。例如，字符串 "abc" 的循环同构字符串包括 "abc" 、 "bca" 和 "cab" 。最小表示法就是找到这些循环同构字符串中字典序最小的那个。

前置知识

字符串循环移位：将字符串的前 $k$ 个字符移到字符串的末尾，形成新的字符串。
字典序：字符串比较的一种方式，按字符的 ASCII 码值逐位比较。

~~真不是为了水字数。~~

算法证明

我们需要证明：算法最终返回的起点一定是所有可能起点中字典序最小的。
证明：我们运用反证法。假设存在

m \in[i, i+k]

是最小表示的起点，则从

m

开始的字符串

s_m..

应小于所有其他起点的字符串。
但由于

m \ge i

且

m \le i+k

，从

m

开始的字符串前缀与从

i

开始的字符串前缀有重叠：

s_{m..m + (i+k - m)} = s_{i + (m - i)..i + k}

。而已知

s_{i..i+k} > s_{j..j+k}

，且

j

的位置与

i

无关

（j \ne i）

，因此从

m

开始的字符串会大于从

j

开始的字符串（因为

s_{m..}

的前缀是

s_{i..i+k}

的后缀，而

s_{i..i+k}

整体大于

s_{j..j+k}

），与 “

m

是最小起点” 矛盾。因此

[i, i+k]

中的所有起点均不可能是最小表示。
算法的时间复杂度由

i、j、k

的总移动次数决定。三者的总移动次数不超过

2n

，因此整体复杂度为

O(n)

。完全可以处理题目给的数据范围。

思路

那我们该如何去求字符串的最小表示呢？
我们先扩展字符串，相当于把它再复制一遍然后加到原来字符串的后面，这样做是为了便于处理循环移位。
接下来我们初始化指针。令 i = 0 和 j = 1 分别表示两个可能的最小表示的起始位置。令 k = 0 表示当前比较的长度。
然后比较 s[i + k] 和 s[j + k]：如果相等，

k

增加

1

，继续比较下一个字符。当它们不相等时：如果 s[i + k] 大于 s[j + k]，说明从

i

开始的子串不可能是最小表示，将

i

移动到

i + k + 1

。反之，将

j

移动到

j + k + 1

。确保

i

和

j

不相等，如果相等则将

j

加

1

。
最终，

i

和

j

中较小的那个就是最小表示的起始位置。
输出从起始位置截取长度为

n

的子串，即为所求的最小表示。

code

CPP

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main(){
    cin>>n>>s;
    s=s+s; // 复制字符串以处理循环移位
    int i=0,j=1,k=0;
    while(i<n&&j<n&&k<n){//开始处理循环移位 
        if(s[i+k]==s[j+k]){
            k++;
        }
		else{
            if(s[i+k]>s[j+k]){
                i=i+k+1;
            }
			else{
                j=j+k+1;
            }
            if(i==j){
                j++;
            }
            k=0;
        }
    }    
    int start=min(i,j);//确定最小表示的起始位置
    cout<<s.substr(start,n); //直接输出 
    return 0;//朴实无华的结尾 
}

如果觉得写的好的请点个赞再走呗。
管理大大求过 QAQ 。

题解：P13270 【模板】最小表示法

文章操作