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

· · 题解

最小表示法的概念

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

前置知识

真不是为了水字数。

算法证明

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

#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 。