KMP（模板)

kmp算法是解决单模匹配问题的算法，难点在于求next[]数组

求next[]数组：对于子串的所有前缀子串的最长公共前后缀的长度，就是next[]数组的值

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。如下图所示：

下面再以”ABCDABD”为例，进行介绍：

”A”的前缀和后缀都为空集，共有元素的长度为0；

”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

eg:主串为cbbbaababac 子串为ababac

初始化next[0]=-1;

子串的最长公共前后缀长度

a -->0 next[1]=0 a的前缀为空，后缀也为空，共有元素的长度为0

ab -->0 next[2]=0 ab前缀为[a]，后缀为[b]，共有元素的长度为0

aba -->1 next[3]=1 前缀为[a，ab]，后缀为[a，ba]，共有元素的长度为1

abab -->2 next[4]=2 前缀为[a，ab，aba]，后缀为[b，ab，bab]，共有元素的长度为2

ababa -->3 next[5]=3 前缀为[a,ab,aba,abab]，后缀也为[a,ba,aba,baba]，共有元素的长度为3

next[i]数组的作用是在当子串字母s[i]在和主串字母p[j]失配的时候,next[i]数组提供一个值，子串整体移动( i-next[i] )个位置，继续用s[next[i]]去和主字母p[j]匹配

eg:模板串是cbbbaababac，子串是ababa

子串下标： 0 1 2 3 4

a b a b a

失配跳转位置next[]： -1 0 0 1 2

这里解释一下：当子串和主串失配的时候,就根据next[]的值移动子串到相应位置去和主串匹配。当子串next[]值为-1的时候，主串的当前匹配位置后移一个字母

这里模拟一下匹配过程，i表示主串的当前匹配位置，j表示子串的当前匹配位置，初始i=0,j=0;主串p[],子串s[]

a!=c ---> i++ i=1,j=0

a!=b ---> i++ i=2,j=0

a!=b ---> i++ i=3,j=0

a!=b ---> i++ i=4,j=0

a==a ---> i++,j++ i=5,j=1

b!=a ---> i保持不变，j=next[j],跳转 i=5,j=0

a==a ---> i++,j++ i=6,j=1

b==b ---> i++,j++ i=7,j=2

a==a ---> i++,j++ i=8,j=3

b==b ---> i++,j++ i=9,j=4

a==a ---> i++,j++ i=10,j=5

j>=strlen(s) 匹配结束，返回可以匹配的首地址 return j-i+1

#include<iostream>

#include<string.h>

using namespace std;

char p[],s[];

int next1[];

void get_next(char *s,int *next1)

{

    int m=strlen(s);//子串的长度

    int j=;//当前匹配的位置

    int k=-;//失配的时候要跳转的位置(也是最长公共前后缀的长度)

    next1[]=-;

    while(j<m)

    {

        if(k==-||s[j]==s[k])

            next1[++j]=++k;

        else

            k=next1[k];

    }

}

int kmp(char *p,char *s)//p是模板串，s是子串

{

    int i=,j=;

    int n=strlen(p);

    int m=strlen(s);

    while(i<n&&j<m)

    {

        if(j==-||p[i]==s[j])

        {

            i++;

            j++;

        }

        else

            j=next1[j];

    }

    if(j>=m)//s串比较完毕

        return i-m+;

    else

        return -;

}

int main()

{

    cin>>p>>s;

    get_next(p,next1);

    for(int i=;s[i];i++)

        cout<<"next["<<i<<"]="<<next1[i]<<endl;

    cout<<"从第"<<kmp(p,s)<<"个字符开始匹配"<<endl;//返回的是开始匹配的第几个字符，不是位置

    return ;

}

巴特西

KMP（模板)

最新文章

热门文章