首页 > 其他 > 详细

KMP - CF126B Password

时间:2019-03-05 14:11:31      阅读:141      评论:0      收藏:0      [点我收藏+]

一道KMP的题。

 

  知识点:1.kmp[i]可能等于0

      2.手玩是个好东西

     

for(int i = k + 1;i < lena;i++)
    {
        if(kmp[i] >= k)
        {
            if(k != 0)
            for(int i = 1;i <= k;i++)printf("%c",c[i]);
            return 0;
        }
    }

 

3.这一段查找1~i这段串中是否有前缀个人觉得是比较妙的。

 

 

 

#include <bits/stdc++.h>
using namespace std;
char c[3000002];
int kmp[3000002];
int lena;
int main()
{
    scanf("%s",c + 1);
    lena = strlen(c + 1);
    int j = 0;
    for(int i = 2;i <= lena;i++)
    {
        while(j && c[j + 1] != c[i])j = kmp[j];
        if(c[j + 1] == c[i])j++;
        kmp[i] = j;
    }
    int k = kmp[lena];
    if(k == 0)//错误1:没想到kmp[lena]可能等于0,导致一开始有一个点没输出。
    {
        printf("Just a legend");
        return 0;
    }
    for(int i = k + 1;i < lena;i++)
    {
        if(kmp[i] >= k)
        {
            if(k != 0)
            for(int i = 1;i <= k;i++)printf("%c",c[i]);
            return 0;
        }
    }
    if(kmp[k] == 0 || k == 0)
    {printf("Just a legend");
        return 0;
    }
    else 
    {
        for(int i = 1;i <= kmp[k];i++)printf("%c",c[i]);
        return 0;
    }
    
    return 0;
}

 

KMP - CF126B Password

原文:https://www.cnblogs.com/xyj1/p/10476267.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!