字符串--Kmp详解+代码

字符串查找问题:

        给定文本串text和模式串pattern,要求从文本串中找到模式串第一次出现的位置。

 解法：

         暴力解法（Brute Force）:      时间复杂度O（M*N），空间复杂度O（1）.

        kmp算法是对BF算法的改进，它是一种线性复杂度的算法，时间复杂度O（N），空间复杂度O（M）。  

    * 记文本串长度N,模式串M。   

暴力求解：

对每个文本字符（假设位置为i）匹配，从模式串第一个位置开始向后匹配，相同往后，不同则从i+1重新匹配。

kmp:

我们先假设有这样一种情况:要匹配的模式串没有一个相同，那你能想到一种线性复杂度的算法吗？

     假设目前A和B部分匹配上了，长度相同，i和j位置字符不同，按照暴力解法，我们要从k+1位置接着匹配。

   但是现在有前提条件：假设匹配串全都不同 那是不是只要从i位置重新匹配就行了。

 考虑这个很强的条件带给我们什么？   

       没错，就是匹配串的重复程度让我们知道从什么位置开始匹配更合理。

        搞定了匹配程度，kmp算法就很jian简单了。

step1：

         开一个数组next存储这种匹配程度，对于模式串的位置j,有next[j]=k,即

     p[0]~p[k-1]==p[j-k]~p[j-1].  则对位置j+1,考察p[j]

1.p[j]==p[k]

     next[j+1]=next[j]+1.

    2.p[j]!=p[k]

    记h=next[k];如果p[h]==p[j],则next[j+1]==h+1,

    重复此过程，若将h改为k,就是一个递归的过程。

最好自己画一下。

实现代码及其简单：

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000000;
char p[maxn],s[maxn];
int next[maxn];
int pattern_len;
void getnext()
{
	pattern_len=strlen(p);
	next[0]=-1;
	int k=-1,j=0;
	while(j<pattern_len-1)
	{
		if(k==-1||p[j]==p[k])
		{
			++j; ++k;
			next[j]=k;
		}else{
			   k=next[k];
		     }
	}
	
}
int kmp()
{
    int	ans=-1;
	int i=0,j=0;
	int n=strlen(s);
	while(i<n)
	{
		if(j==-1||p[j]==s[i])
		{
			i++; j++;
		}else  j=next[j];
		if(j==pattern_len)
		{
			ans=i-pattern_len+1;//字符以0开始，位置加一 
			break;
		}
	}
	return ans;
}
int main()
{
	while(1)
	{
		scanf("%s",s);//文本串 
		scanf("%s",p);//匹配串 
		getnext();
		
		printf("%d\n",kmp());
	}
	
  return 0;	
}