字符串匹配（BF算法和KMP算法）

看了老师的录频，感觉还是得自己动手写写，不然估计可能不太懂,哈哈，那我们就先来看一下BF算法：

我们先来看一个例子：现有这样的一个字符串“ababcabcdabcde”和“abcd”;

BF算法应该是这样的：

不知道大家看懂了没，没关系，我们再来看一下代码再捋捋。

int BF(const char *s,const char *sub,int pos)
{
	int i = pos;
	int j = 0;
	int lens = strlen(s);
	int lensub = strlen(sub);
	while(i=lensub)
	{
		return i-j;
	}
	else
	{
		return -1;
	}
}
int main()
{
	char *s = "ababcdabe";
	char *sub = "abcd";
	cout< 
 
结果：
 
 

 
 
总结：不知道大家发现没有，i每次都需要回退到i-j+1处，但是就拿第一次匹配失败来说，i指向b,j指向a,b和a明显不相同，i就没有必要回退了。
 
 
那我们现在来看一下KMP算法，这个还不怎么好解释，画图先看看。
 
 
我们先来举一个例子s:abcababcabc        sub:abcabc
 
 
此时i指向s串的a，j指向sub的a,开始匹配，一直到：i指向s的第三个a，j指向sub的最后一个c，发现此刻不匹配，但是我们现在不需要将i回退，我们只需要将j回退到适当的k的位置上，
 
 

 
 
那么现在，最起码我们不用再将i回退，j也不用回退到原来的0的位置上了。
 
 
但是现在，我们最重要的是，怎么才能找到这个合适的k呢？？？？？？？？
 
 
我们再来看图：
 
 

 
 
这样我们就会轻易的发现，红色下划线的两个字符串相等，由于我们是在a和c的时候匹配失败的，所以我们取之前他的子集也是匹配的，所以蓝色下划线的两个字符串也是相等的，那么我们自然也可以推出在sub串中，红色下划线的字符串和蓝色下划线的字符串是相等的
 
 
那我们用表达式把它表达出来：
 
 
从P0......Pk-1  =  Px.......Pj-1;(x的位置我们现在还不知道)
 
 
那么就又有了：k-1-0 = j-1-x;那么就可以推出x = j-k;
 
 
那么也就有了：P0......Pk-1 = Pj-k......Pj-1;
 
 
那么其实我们也可以换种方式说：我们要找到匹配成功部分的两个相等的真字串，一个以0下标开头，一个以j-1下标结尾。
 
 
那么我要做的是将sub每一个可能出现失配的所有的k值next数组来保存。
 
 
现在我们来求一下每一个下标的k值：
 
 
以a  b  a  b  c  a  b  c  d  a  b  c  d  e
 
 
next[0] 我们初始为-1；
 
 
next[1]:a         b  a  b  c  a  b  c  d  a  b  c  d  e,真字串长度为0,  next[1] = 0;
 
 
next[2]:a  b         a  b  c  a  b  c  d  a  b  c  d  e,真字串长度为0，next[2] = 0;
 
 
next[3]:a  b  a         b  c  a  b  c  d  a  b  c  d  e,真字串长度为1，next[3] = 1;
 
 
next[4]:a  b  a  b         c  a  b  c  d  a  b  c  d  e,真字串长度为2，next[4] = 2;
 
 
next[5]:a  b  a  b  c         a  b  c  d  a  b  c  d  e,真字串长度为0,  next[5] = 0;
 
 
next[6]:a  b  a  b  c   a        b   c  d  a  b  c  d  e,真字串长度为1,  next[6] = 1;
 
 
next[7]:a  b  a  b  c   a  b         c  d  a  b  c  d  e,真字串长度为2,  next[7] = 2;
 
 
next[8]:a  b  a  b  c  a  b  c         d  a  b  c  d  e,真字串长度为0,  next[8] = 0;
 
 
next[9]:a  b  a  b  c  a  b  c  d         a  b  c  d  e,真字串长度为0,  next[9] = 0;
 
 
next[10]:a  b a  b  c  a  b  c  d   a        b  c  d  e,真字串长度为1,  next[10] = 1;
 
 
next[11]:a  b   a  b  c  a  b  c  d a  b       c  d  e,真字串长度为0,  next[11] = 2;
 
 
next[12]:a  b  a  b  c  a  b  c  d  a  b  c       d  e,真字串长度为0,  next[12] = 0;
 
 
next[13]:a  b  a  b  c  a  b  c  d  a  b  c   d       e,真字串长度为0,  next[13] = 0;
 
 
哇，打的我快吐血了
 
 
那我们怎么用代码来求这个next数组呢（上面是我们手动求的）：
 
 
首先，不管是怎么样的字符串，我们都有next[0] = -1,next[1] = 0;那么如果我们能通过next[i]的值来推出next[i+1]的值，那我们就万事大吉了，那么我们就要找next[i]和next[i+1]d的关系：
 
 
那我们不妨先假设next[j] = k;那么就有：P0.....Pk-1   =   Pj-k.....j-1.
 
 
如果Pk = Pj;我们就能推出：P0.......Pk =  Pj-k........Pj  =>  next[i+1] = k+1;
 
 
例如：
 
 
 
 
next[6]:a  b  a  b  c  a        b   c  d  a  b  c  d  e, next[6] = 1;//k等于1，
 
 
next[7]:a  b  a  b  c  a  b         c  d  a  b  c  d  e, next[7] = 2;//此时k= 1,j =6：P0.....P1  =  P5......P6(P0....Pk = Pj-1......Pj) ,那么next[7] = k+1 = 2;
 
 
qi其实说白了就是新增的两个字符是相等的。。。。
 
 
那么还有第二种可能就是Pj != Pk
 
 
我们重新举个例子：
 
 

 
 

 
 
注意是：k = next[k];我们刚刚是在2的位置上失配的。。。。。。
 那我们现在看一下代码的实现： 
 
 
 
void GetNext(int *next,const char *sub)
{
	int lensub = strlen(sub);
	next[0] = -1;
	next[1] = 0;
	int i = 2;//i已经加1了
	int k = 0;
	while(i=lensub)//找到了
		return i-j;
	else
		return -1;
}
int main()
{
	char *s = "ababcdabe";
	char *sub = "abcd";
	cout<