最小表示法

定义#

最小表示法是用于解决字符串最小表示问题的方法。

循环同构#

当字符串中可以选定一个位置满足

则称与循环同构

最小表示#

字符串的最小表示为与循环同构的所有字符串中字典序最小的字符串

算法核心#

考虑对于一对字符串 , 它们在原字符串中的起始位置分别为 , 且它们的前个字符均相同，即

不妨先考虑的情况，我们发现起始位置下标满足的字符串均不能成为答案。因为对于任意一个字符串（表示以为起始位置的字符串，）一定存在字符串比它更优。

所以我们比较时可以跳过下标 , 直接比较

这样，我们就完成了对于暴力的优化。

时间复杂度#

过程#

初始化指针为，为；初始化匹配长度为
比较第位的大小，根据比较结果跳转相应指针。若跳转后两个指针相同，则随意选一个加一以保证比较的两个字符串不同
重复上述过程，直到比较结束
答案为中较小的一个

实现#

int n,a[300005];
int main(){
    n=read();
    for(int i = 0;i< n;i++) a[i]=read();
    int i = 0,j = 1,k = 0;
    while(i<n&&j<n&&k<n){
        if(a[(i+k)%n]==a[(j+k)%n])k++;
        else{
            a[(i+k)%n]>a[(j+k)%n]? i=i+k+1:j=j+k+1;
            if(i==j)i++;
            k=0;
        }
    }
    i = min(i,j);
    for(int cnt=1;cnt<=n;cnt++){
        cout<<a[i]<<" ";
        i=(i+1)%n;
    }
    return 0;
}

cpp

定义#

循环同构#

最小表示#

算法核心#

时间复杂度#

过程#

实现#

Comments