KMP 算法

KMP 算法 与 朴素算法相比少了不必要的重复工作，比如ABABCD串在C处失配应从第二个A处匹配，不是第一个A处匹配。所以KMP的关键是状态转移表（预处理时间是0（M）），总的时间复杂度是0（M + N）。

状态转移就是模式串每个位置的最大相等子串。

前提：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char w[10010];
char t[1000010];
int next[10010];
int cnt;

void get_next()
{
	next[0] = 0;
	next[1] = 0;
	int j ;
	for(int i = 1; w[i]!= ‘\0‘; i ++)
	{
		j = next[i]; 
		while(j && w[j] != w[i]) j = next[j];
		next[i+1] = w[j] == w[i] ? j + 1: 0;
	}
}

则next[i+1] = L+1(0 ,1,2,3,....,L),如果w[i] ！= w[j](w[i] ！= w[L])，最大相等子 串为0，next[i+1] = 0;

匹配过程：

void kmp()
{
	int j = 0 , m = strlen(w); 
	for(int i = 0; t[i] != ‘\0‘; i ++)
	{
		while(j && w[j] != t[i]) j = next[j];
		if(w[j] == t[i]) j ++;
		if(j == m) cnt ++;
	}
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char w[10010];
char t[1000010];
int next[10010];
int cnt;
void get_next()
{
	next[0] = 0;
	next[1] = 0;
	int j ;
	for(int i = 1; w[i]!= ‘\0‘; i ++)
	{
		j = next[i]; 
		while(j && w[j] != w[i]) j = next[j];
		next[i+1] = w[j] == w[i] ? j + 1: 0;
	}
}

void kmp()
{
	int j = 0 , m = strlen(w); 
	for(int i = 0; t[i] != ‘\0‘; i ++)
	{
		while(j && w[j] != t[i]) j = next[j];
		if(w[j] == t[i]) j ++;
		if(j == m) cnt ++;
	}
}
int main()
{
	int n ;
	scanf("%d",&n);
	while(n --)
	{
		scanf("%s",w);
		nex();
		cnt = 0;
		scanf("%s",t);
		kmp();
		cout << cnt << endl;
	}
	return 0;
}

KMP 算法,布布扣,bubuko.com

KMP 算法

原文：http://blog.csdn.net/wuhuajunbao/article/details/22900491