Skip to content

最小表示法

什么是

用于求S的循环同构串的最小字典序

时间复杂度O(n)

如何

引自OI WIKI

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

模板

例题

cpp
int n=read();
int a[n*2];
For(i,0,n){
    a[i]=read();
    a[i+n]=a[i];
}
int i=0,j=1,k=0;
while(i<n&&j<n){
    while(a[i+k]==a[j+k])k++;
    if(a[i+k]>a[j+k])i+=k+1;
    else j+=k+1;
    k=0;
    if(i==j)j++;
}
int st=min(i,j);
For(i,st,st+n){
    char f=' ';
    if(i==st+n-1)f=endl;
    cout<<a[i]<<f;
}

网站基于vitepress主题open17💙