最小表示法

理论学习

给定一个字符串 $s$，首尾相接（循环同构），找到其字典序最小的情况 $O(n)$

用两个指针 $i,j$，分别指向目前两个可能是答案的起始位置
初始 $i = 1, j = 2$，随着算法进行增大
假设现在 $i < j$，且从 $i$ 开始的 $k$ 位字符和从 $j$ 开始的 $k$ 位字符是一样的，此时这两段子串相同
如果 $s[i+k] \neq s[j+k]$
谁大谁往后移动 $k+1$ 个位置
如果 $s[i+k] == s[j+k]$
随便移动一个
最后小于 $n$ 的那个指针就是所求答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


void getmin(string s){
    int n=s.size();
    s=s+s;
    int i=0,j=1;
    while(j<n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])
            ++k;
        if(s[i+k]>s[j+k])
            i+=k+1;
        else 
            j+=k+1;
        if(i==j)j++;
        if(i>j)swap(i,j);
    }
    for(int k=i;k<=i+n;k++)cout<<s[k];
}

例题

循环同构判断

给定两个字符串 $a, b$，判断两个字符串是否循环同构

只需判断两个字符串最小表示是否一样即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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

string a,b;

int getmin(string s){
    int n=s.size();
    int i=0,j=1;
    s=s+s;
    while(j<n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])++k;
        if(s[i+k]>s[j+k])i+=k+1;
        else j+=k+1;
        if(i==j)++j;
        if(i>j)swap(i,j);   
    }
    return i;
}

int main(){
    cin>>a>>b;
    for(int i=getmin(a),j=getmin(b),k=0;k<n;k++){
        if(a[(i+k)%n]!=b[(j+k)%n]){
            cout<<"NO\n";
            return 0;
        }
    }
    cout<<"YES\n";
}

最小循环覆盖

给出字符串 $a$，求出这个字符串的字典序最小的最小循环覆盖

先用 $kmp$ 求出最小循环片段长度，再求这个长度的子串的最小表示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


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

string a;
int nxt[100005];

int kmp(){
    int n=a.size();
    nxt[0]=0;
    int j=0;
    for(int i=1;i<n;i++){
        while(j&&a[i]!=a[j])
            j=nxt[j-1];
        if(a[i]==a[j])
            j++;
        nxt[i]=j;
    }
    return n-nxt[n-1];
}

void getmin(string s,int n){
    s=s+s;
    int i=0,j=1;
    while(j<n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])++k;
        if(s[i+k]>s[j+k])i+=k+1;
        else j+=k+1;
        if(i==j)j++;
        if(i>j)swap(i,j);
    }
    for(int l=i;l<i+n;l++)cout<<s[l];
}

int main(){
    cin>>a;
    getmin(a,kmp());
    return 0;
}