最小表示法(模板) CH1807

最小表示法(模板) 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
*/

 

上一篇:HDU - 5955 Guessing the Dice Roll(AC自动机 高斯消元解dp方程)


下一篇:KMP poj3942