首页 > 其他 > 详细

LibreOJ #103. 子串查找

时间:2017-06-25 14:42:36      阅读:390      评论:0      收藏:0      [点我收藏+]

二次联通门 : LibreOJ #103. 子串查找

 

 

 

 

/*
    LibreOJ #103. 子串查找
    
    kmp
     
*/
#include <cstdlib>
#include <cstring>
#include <cstdio>

#define Max 1000900

int next[Max];

void Get_Next (char *line)
{
    next[0] = -1;
    
    for (register int pos_1 = 0, pos_2 = -1, Len = strlen (line); pos_1 < Len; )
        if (pos_2 == -1 || line[pos_1] == line[pos_2])
        {
            pos_1 ++;
            pos_2 ++;
            next[pos_1] = pos_2;
        }
        else
            pos_2 = next[pos_2];

}

int Answer;

void Kmp (char *line, char *__txt)
{
    int Len_txt = strlen (__txt);
    int Len_ = strlen (line);
    
    if (Len_txt < Len_)
    {
        puts (0);
        exit (0);
    }
    for (register int pos_1 = 0, pos_2 = 0; pos_2 < Len_txt && pos_1 < Len_; )
    {
        if (pos_1 == -1 || line[pos_1] == __txt[pos_2])
        {
            pos_1 ++;
            pos_2 ++;
        }
        else
            pos_1 = next[pos_1];
        if (pos_1 == Len_)
        {
            Answer ++;
            pos_1 = next[pos_1];
        }
    }
}

char line[Max];
char __txt[Max];

int main (int argc, char *argv[])
{
    scanf ("%s", __txt);
    scanf ("%s", line);
    
    Get_Next (line);

    Kmp (line, __txt);
    printf ("%d", Answer);
    
    return 0;
}

 

LibreOJ #103. 子串查找

原文:http://www.cnblogs.com/ZlycerQan/p/7076732.html

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