最小表示法

SalN · 2022-10-21 13:12:16 · 算法·理论

对于一个字符串 S, 可以随意把祂头部的放到尾部，这样弄出来最小的字符串 \min\{S'\} 就是 S 的最小表示（

通过这种方法，我们可以快速搞同构串 qwq

我们先 断环成链，那么就变成了找长度为 n=|S| 的最小子串

我们用 x 对应 S[x],...,S[x+n-1] 这个串

我们考虑比较 i,j 的优劣，首先考虑 BF，那么我们比较 S[i] 和 S[j]，S[i+1] 和 S[j+1]，...，直到出现第一个 S[i+k] 跟 s[j+k] 不相等，或者发现 i,j 对应的串等同

我们很容易发现，因为 S[i],...,S[i+k-1] 跟 S[j],...,S[k+j-1] 的等同，那么根据 S[i+k] 与 S[j+k] 的优劣，肯定有 i,j 之一的 x 对应的 [x,x+k] 不能成为最小表示，通过这种方法，我们可以弄一个 O(N) 的算法，复杂度在算法里有很好的体现（

唔，对于扫完循环元的情况可以先跑出来（

#include<bits/stdc++.h>
#define MN 601000

using namespace std;

int n, a[MN];

signed main() {
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        a[i+n]=a[i];
    }
    int i=1, j=2, k;
    while(i<=n&&j<=n) {
        for(k=0; k<=n; ++k)
            if(a[i+k]!=a[j+k]) break;
        if(k==n) break;
        if(a[i+k]>a[j+k]) i=i+k+1;
        else j=j+k+1;
        if(i==j) i++;
    }
    for(k=min(i,j); k<min(i,j)+n; ++k)
        printf("%d ", a[k]);
    return 0;
}