串的模式匹配
串的模式匹配也可以说子串的定位，是一种重要的串运算。所谓模式匹配就是给定两个串s1和s2，在主串s1中找到子串找到一个子串等于s2的过程。对于这样的运算一般有两种方法，一种是暴力的匹配方法，而另一种则是KMP算法。
暴力的匹配方法
int BruteFroce(char s1[],char s2[])
{
int i=0,j=0;
int len1 = strlen(s1),len2=strlen(s2);
while(i<len1 && j<len2)
{
//如果当前位置匹配成功，则i和j同时移动
if(s1[i]==s2[j])
{
i++;
j++;
}
else
{
//如果不成功，则i回到匹配前的下一个位置
i = i-j+1;
//子串从头开始匹配
j = 0;
}
}
//匹配成功放回子串在主串的位置
if(j==len2)
return i;
else //匹配失败返回-1
return -1;
}
从这段代码可以看得出，的确很暴力，逐项进行比较，对应位置的字符相等就继续移动，否则就跳出内层循环，让j回到起点，让i回到刚刚匹配成功的点的下一个位置，这种匹配的时间复杂度是（len1*len2），然而有一种叫做kmp的算法比他快，时间复杂度是O（len1+len2），之所以快的原因是减少了很多在匹配过程中不必要的回退。
kmp算法
next数组
kmp算法比起直接暴力的之所以快，是因为它没有像暴力法回退的那么
鲁莽（一口气就跑回去了），而kmp先预处理一遍用了一个next数组
储存当前位置前缀和后缀（除去本身）最大相等的长度。
那么next存储了这些数字有什么用呢？其实当存储了前缀和后缀最大
相等的长度后有个很好的地方就是，如果在当前未知匹配失败了，j是
要往回跑的，但是没有必要跑到底，可以根据next数组来判断回到
哪里。
举个例子
比如一个字符串为"abcaabc"
对于第0个位置来说，因为除去本身，所以前缀和后缀的最大长度为0
对于第1个位置来说，因为‘a’和‘b’不相等，所以前缀和后缀的最大长度为0
对于第2个位置来说，‘a’和‘c’不相等，‘ab’和'bc'不相等，所以前缀和后缀的最大长度为0
对于第3个位置来说，‘a’和'a'相等，所以前缀和后缀的最大长度为1
对于第4个位置来说，‘a’和‘a’相等，所以前缀和后缀的最大长度为1
对于第5个位置来说，‘ab’和‘ab’相等，所以前缀和后缀的最大长度为2
对于第6个位置来说，‘abc’和‘abc’相等，所以前缀和后缀的最大长度为3
|位置 | 0 | 1 | 2 | 3| 4 | 5 | 6 |
|-------|:-------------------------|
|模式串 | a | b | c | a | a | b | c |
|所以前缀和后缀的最大长度为 | 0 | 0 | 0 | 1 | 1 | 2 | 3 |
而next数组只需要把上面存储的值同一向右挪动一个单位，然后next[0]赋值为-1，这样挪移的意思就是不包含当前位置的最大前缀和后缀的长度，所以存储结果为：
|位置 | 0 | 1 | 2 | 3| 4 | 5 | 6 |
|-------|:-------------------------|
|模式串 | a | b | c | a | a | b | c |
|next数组 | -1 | 0 | 0 | 0 | 1 | 1 | 2 |
next数组的求法
那么next数组怎样来求呢？
其实我们可以这样来理解，假设这个next数组已经写到了第k位，让你来写第k+1位，那么怎么写呢，因为第k为记录的是前k-1个元素最大公共长度，那么如果第k个元素等于s[next[k]+1]的话s[k+1] = next[k]+1
代码实现
#define MAXSIZE 1000
int next[MAXSIZE];
void GetNext(char *s)
{
next[0] = -1;
int len = strlen(s);
int i=0,k=-1;
while(i<len)
{
//s[k]表示前缀，s[i]表示后缀
if(k==-1 || s[k]==s[i])
{
i++;
k++;
//如果相等则下一个位置next[i+1]=k+1
next[i] = k;
}
else
k = next[k];
}
}
kmp的实现
由图中可以看出，next数组指引了当前位置不匹配时怎么走下一步，没有必要直接让模式串从头开始比较
其实kmp主要是next数组那一部分的理解，如果理解了next数组和他在kmp中的工作原理，那么kmp理解就差不多了。
//s1主串，s2模式串
//获取子串的位置
int kmp(char *s1,char *s2)
{
//获取next数组
GetNext(s2);
int i,j=0;
int len1 = strlen(s1);
int len2 = strlen(s2);
while(i<len1 && j<len2)
{
//j==-1或匹配成功则继续下去
if(s1[i]==s2[j])
{
j++;
i++;
}
else if(j==0) //如果当前为匹配不成功，且j=0，那么只需要i++就好
i++;
else
{
//如果j！=0且当前位置匹配不成功j回到next[j]的位置
j = next[j];
}
}
//匹配成功返回子串位置，否则返回-1
if(j==len1)
return i-j;
else
return -1;
}
//用kmp计算子串出现的次数
int kmp_count(char *s1,char *s2)
{
//获取next数组
GetNext(s2);
int i,j=-1，count=0;
int len1 = strlen(s1);
int len2 = strlen(s2);
while(i<len1)
{
if(a[i]==b[j])
{
i++;
j++;
}
else if(j==0)
i++;
else
j = nex[j];
if(j==len2)
{
count++;
j = nex[j]; //子串可以相互重叠
//j=0 计算不重叠子串的数量
}
}
//返回子串出现的次数
return count;
}
kmp练练手
学习当中参考的博客
从头到尾彻底理解KMP
网友评论