Loading...

Kmp 字符串匹配算法 洛谷P3357

check评论:0 条 remove_red_eye浏览量:393 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-04

很好的博客
求$next$数组:

void getnext()
{
    int n=strlen(p);
    fail[0]=0;
    for(int i=1;i<n;i++)
    {
        int j=fail[i];
        while(j&&p[i]!=p[j])
        {
            j=fail[j];
        }
        fail[i+1]=p[i]==p[j]?j+1:0;
    }
}

$kmpsearch$:

int kmpsearch()
{
    int n=strlen(mos);
    int m=strlen(p);
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j&&mos[i]!=p[j])
        {
            j=fail[j];
        }
        if(mos[i]==p[j])
        {
            j++;
            if(j==m)
            {
                printf("%d\n",i-m+2);
                j=fail[j];
            }
        }
        else
        {
            j=fail[j];
        }
    }
}

完整代码:

#include <bits/stdc++.h>
using namespace std;
char p[1000010];
int fail[1000010];
char mos[1000010];
void getnext()
{
    int n=strlen(p);
    fail[0]=0;
    for(int i=1;i<n;i++)
    {
        int j=fail[i];
        while(j&&p[i]!=p[j])
        {
            j=fail[j];
        }
        fail[i+1]=p[i]==p[j]?j+1:0;
    }
}
int kmpsearch()
{
    int n=strlen(mos);
    int m=strlen(p);
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j&&mos[i]!=p[j])
        {
            j=fail[j];
        }
        if(mos[i]==p[j])
        {
            j++;
            if(j==m)
            {
                printf("%d\n",i-m+2);
                j=fail[j];
            }
        }
        else
        {
            j=fail[j];
        }
    }
}
int main()
{
    scanf("%s%s",mos,p);
    getnext();
    kmpsearch();
    int kkk=strlen(p);
    for(int i=1;i<=kkk;i++)
    {
        printf("%d ",fail[i]);
    }
}

洛谷P1250 种树 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名