浅谈KMP算法

文章转自我的csdn博客

被遮住代码块：

1.

bool check(int pos)

{

    for(int i=pos,j=0;j<m;i++,j++)

        if(text[i]!=pattern[j])

            return false;

    return true;

}

void solve()

{

    //n表示text长度，m表示pattern长度

    int ans=-1;

    for(int i=0;i<n;i++)

        if(check(i))

            ans=i,break;

    cout<<ans<<endl;

}

2.

void get_next()

{

next[0]=-1;//在0这个位置不存在任何最大前后缀（情况三）

int k=-1;

for(unsigned int i=1;i<pattern.size();i++)

{

while(k>-1 && pattern[k+1] != pattern[i])//情况二

k=next[k];

if(pattern[k+1]==pattern[i])//情况一

k++;

next[i]=k;

}

}

3.

void kmp()

{

int k=-1;

for(unsigned int i=0;i<text.size();i++)

{

while(k>-1 && pattern[k+1]!=text[i])

k=ne[k];

if(pattern[k+1]==text[i])

k++;

if(k==pattern.size()-1)

{

return i-k;

}

}

return -1;

}