数据结构-模式匹配串算法(KMP)

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

void getnext(char *t, int *next, int lent)

{

    int i = 0, j = -1;

    next[0] = -1;

    while (i < lent)

        if (j == -1 || t[i] == t[j])

            ++i, ++j, next[i] = j;

        else

            j = next[j];

}

int kmp(char *s, char *t, int *next, int lens, int lent)

{

    int i = 0, j = 0;

    while (i < lens)

    {

        if (-1 == j || s[i] == t[j])

            i++, j++;

        else

            j = next[j];

        if (j == lent) return 1;

    }

    return 0;

}

int main()

{

    char t[100],s[1000];

    int next[100];

    printf("Enter模式串，主串\n");

    scanf("%s",t);

    gets(s);

    int lent = strlen(t);

    int lens = strlen(s);

    getnext(t, next, lent);

    printf("%d\n1表示成功", kmp(s, t, next, lens, lent));

    return 0;

}

巴特西

数据结构-模式匹配串算法(KMP)

最新文章

热门文章