最小表示法

尼古拉夫斯7 lv.1

发布时间：2022-11-07 18:24:32 336

最小表示法

参考：最小表示法

目的：O(n)求出一个序列循环同构中最小的那一个（在字符串中表示为字典序最小的一个循环同构）

优化内容：i，j 分别是当前比较的起始下标，k 是已比较的个数。当前假设\(A_{i+k}>B_{j+k}\)，那么对于\(i+p(i\le i+p\le i+k)\)起始的字符串，\(S_{j+p}\)一定比它更优，所以这一段可以直接跳过。

#include
using namespace std;
const int maxn=3e5+5;
int a[maxn];

int main(){
    int n;cin>>n;
    for(int i=0;i>a[i];
    int k=0,i=0,j=1;
    while(k        if(a[(i+k)%n]==a[(j+k)%n]) k++;
        else{
            if(a[(i+k)%n]>a[(j+k)%n]) i+=k+1;
            else j+=k+1;
            if(i==j) ++i;
            k=0;
        }
    }
    int op=min(i,j);
    for(i=0;i        cout<}

CAD加油！欢迎跟我一起讨论学习算法

文章来源： https://blog.51cto.com/u_15860211/5820433

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。