最小表示法（模板） CH1807

男娘i 2021-11-01 03:38 280阅读 0赞

# 最小表示法（模板） CH1807 #

## 思路：将原字符串加倍，一段一段暴力比较，复杂度n\*n。通过排除无用比较实现线性求。详见蓝书（算法竞赛指南）P72。 ##

## 注意：1.以1作为下标起始，应该输入时+1！！（易漏） ##

## 　　　2.最小表示法中的while边界是原字符串！！ ##

/*
    题意：
    判断两个串是否是循环同构串（加倍用KMP） 
    如果是，找出其最小表示 （模板） 
    */
    #include<bits/stdc++.h>
    using namespace std;
    #define N 100005
    int lena,lenb,nex[N];
    char a[N*2],b[N*2];
    void get_nex()
    {
        nex[1]=nex[0]=0;
        for(int i=2,j=0;i<=lenb;i++){
            while(j>0&&b[i]!=b[j+1]) j=nex[j];
            if(b[i]==b[j+1]) j++;
            nex[i]=j;
        }
    }
    void work()
    {
        int k=0,i=1,j=2;//i j 的值要随时保持不一样 
        while(i<=lena&&j<=lena)//这里应该是原长！！而不是加倍后的长度 
        {
            for(k=0;k<=lena&&a[i+k]==a[j+k];k++);
            if(k==lena) break;//特殊情况：只有一种字符组成 
            if(a[i+k]>a[j+k]){
                i=i+k+1;
                if(i==j) i++;//i j应该不一样 否则就会把它当特殊情况处理 
            }
            else{
                j=j+k+1;
                if(i==j) j++;
            }
        }
        int ans=min(i,j);//最后答案应该从较小的一个开始 
        for(int kk=ans;kk<=ans+lena-1;kk++) printf("%c",a[kk]);
    }
    void solve()
    {
        int fl=0;
        for(int i=1;i<=lena;i++) a[i+lena]=a[i];
        for(int i=1,j=0;i<=lena*2;i++){
            while(j>0&&(j==lenb||a[i]!=b[j+1])) j=nex[j];
            if(a[i]==b[j+1]) j++;
            //printf("%d\n",j);
            if(j==lenb){ fl=1; break; }
        }
        if(!fl) { printf("No\n"); return ; }
        printf("Yes\n"); work();
    }
    int main()
    {
        scanf("%s%s",a+1,b+1);//一定要记得角标+1！！ 
        lena=strlen(a+1),lenb=strlen(b+1);
        get_nex();
        solve();
    }
    /*
    2234342423
    2423223434
    
    2341
    3412
    */

转载于:https://www.cnblogs.com/mowanying/p/11154007.html