2018年全国多校算法寒假训练营练习比赛(第五场) C KMP-Next数组

Next数组

自己写的卡在%95.00的代码

我自己写的代码,至今想不通漏了什么情况,被卡在%95.00…

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

map<int,int> ex;

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void print(){
    for(int i=1;i<=len;++i){
        printf("%d ",Next[i]);
    }
}

void solve(){
    ex.clear();
    getNext();
    //print();
    int bef=Next[len],now,max_len=0;
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    while(bef!=0){
        now=bef;
        bef=Next[bef];
    }

    for(int i=1;i<=len;++i){
        if(Next[i] && Next[i]%now==0){
            int k=Next[i]/now;
            for(int j=1;j<=k;++j){
                ex[j*now]++;
            }
        }
    }
    map<int,int>::iterator it;
    for(it=ex.begin();it!=ex.end();it++){
        if(it->second>1) max_len=max(max_len,it->first);
    }
    if(max_len){
        max_len=min(max_len,Next[len]);
        for(int i=0;i<max_len;++i){
            printf("%c",str[i]);
        }
    }else printf("Just a legend");
    printf("\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

AC代码

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1001000;
int Next[maxn],len;
char str[maxn];

int exist[maxn];

void getNext(){
    Next[0]=-1;
    int k=-1;
    int j=0;
    while(j<len){
        if(k==-1 || str[j]==str[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void solve(){
    memset(exist,0,sizeof(exist));
    getNext();
    int bef=Next[len];
    if(bef==0){
        printf("Just a legend\n");
        return;
    }
    //忽略第一个和最后一个
    for(int i=2;i<len;++i){
        exist[Next[i]]++;
    }

    while(bef>0){
        if(exist[bef]){
            for(int i=0;i<bef;++i){
                printf("%c",str[i]);
            }
            printf("\n");
            return;
        }
        bef=Next[bef];
    }
    printf("Just a legend\n");
}

int main(){
    while(cin>>str){
        len=strlen(str);
        solve();
    }
    return 0;
}

当然,还有一种方法是比较特别的(比较直观),把每个可能子串KMP一下,如果匹配成功了,就直接输出就好了

#include<cstdio>
#include<cstring>
char a[1000005],b[1000005];
int next[1000006];
void getnext(char *c)
{
    next[0]=next[1]=0;
    int i,j,len=strlen(c);
    for(i=1,j=0;i<len;i++)
    {
        while(c[i]!=c[j]&&j!=0)
            j=next[j];
        if(c[i]==c[j])j++;
        next[i+1]=j;
    }
}
int kmp(char *o,char *f)
{
    int cont=0;
    int i,j,len1=strlen(o),len2=strlen(f);
    for(i=0,j=0;i<len1;i++)
    {
        while(o[i]!=f[j]&&j!=0)
            j=next[j];
        if(o[i]==f[j])j++;
        if(j==len2)
        {
            cont++;
            j=next[j];
        }
    }
    return cont;
}
int main()
{
    int i;
    scanf("%s",a);
    getnext(a);
    int len=next[strlen(a)];
    if(len==0)
    {
        printf("Just a legend\n");
        return 0;
    }
    for(i=0;i<len;i++)
        b[i]=a[i];
    b[i]='\0';
    int cont=kmp(a,b);
    while(cont<3)
    {
        len=next[len];
        if(len==0)break;
        for(i=0;i<len;i++)
            b[i]=a[i];
        b[i]='\0';
        cont=kmp(a,b);
    }
    if(cont>=3&&len)printf("%s\n",b);
    else printf("Just a legend\n");
    return 0;
}

1

2