求子串位置的定位函数index
子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一。
一个最简单的匹配方法是：
从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。
匹配字符串
初始化：
初始化
之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：
比较字符是否一致
A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：
把i指针移回第1位重新开始查找
算法实现如下：
int indexSubStr(MyString *S,MyString *substr,int pos){
int i = pos,j = 0;
while(i < S->length && j < substr->length){
if(*(S->str + i) == *(substr->str + j)){
i++;
j++;
}else{
i = i - j + 1;
j = 0;
}
}
if(j == substr->length){
return i - j;
}else{
return -1;
}
}
上述算法的匹配过程易于理解，且在某些应用场合，如文本编辑等，效率也较高。较好的情况下，此算法的时间复杂度为O(n+m)。然而在有些情况下，该算法的效率却很低。例如，当模式串为“00000001”，而主串为“00000000000000000000000000000001”时，每趟比较都在模式的最后一个字符出现不等，此时需要将指针i重新回溯到i-6的位置上，并从模式的第一个字符开始重新比较，则最坏的情况下的时间复杂度为O(n*m)。
模式匹配的一种改进算法——KMP算法
这种改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其改进在于：每一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的部分匹配的结果，将模式串向右滑动尽可能远的一段距离后，继续进行比较。
如：
比较字符发现不一致
此时，移动j到一个合适的位置k继续比较：
移动j到一个合适的位置k
如下图也是一样的情况：
比较字符发现不一致
此时，移动j到一个合适的位置k继续比较：
移动j到一个合适的位置k
至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。如下图所示：
最前面的k个字符和j之前的最后k个字符是一样的
下面讨论一般情况。假设主串为“s1s2....sn”,模式串为“p1p2...pm”,从上例的分析可知，为了实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即si≠pj）时，模式串“向右滑动”可行的距离多远，换句话说，当主串中第i个字符与模式中第j个字符“失配”时，主串中第i个字符（i指针不回溯）应与模式串中哪个字符再比较？
假设此时应与模式中第k（k<j）个字符继续比较，则模式中前k-1个字符的子串必须满足下列关系式，且不可能存在k’>k满足下列关系式：
“p1 p2 ... pk-1” = “si-k+1 si-k+2 ... si-1”
即下图蓝框圈起的上下两部分：
蓝框圈起的上下两部分
而已经得到的部分匹配的结果是：
“pj-k+1 pj-k+2 ... pj-1” = “si-k+1 si-k+2 ... si-1”
即下图蓝框圈起的上下两部分：
蓝框圈起的上下两部分
那么可以推得下列等式：
“p1 p2 ... pk-1” = “pj-k+1 pj-k+2 ... pj-1” 。
即下图表示的两边相等的部分：
k两边相等的部分
即，若模式中存在满足上式的两个子串，则当匹配过程中，主串中第i个字符与模式中第j个字符比较不等时，仅需将模式串向右滑动至模式中第k个字符和主串中第i个字符对齐，此时，模式中前k-1个字符的子串“p1 p2 ... pk-1”必定与主串中第i个字符之前长度为k-1的子串“si-k+1 si-k+2 ... si-1”相等，由此，匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。
因为在p的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当s[i] != p[j]时，j指针的下一个位置。由此可引出模式串的next函数的定义：
| next[j]= | -1 | 当j = 0时 |
|---|---|---|
| Max{k|0<k<j且“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”} | 当此集合不空时 | |
| 0 | 其他情况 |
求得模式串的next函数之后，匹配可如下进行：
假设以指针i和j分别指示主串和模式中正待比较的字符，令i的初值为pos，j的初值为0。
若在匹配的过程中s[i]=p[j]，则i，j分别增1，继续比较；
若s[i]≠p[j]，则i不变，而j退到next[j]的位置再比较，若相等，则指针各自增1，否则j再退到next[j]的位置再比较，以此类推；
若j退到值为0，则此时需将模式串继续向右滑动一个位置，即从主串的下一个字符si+1起和模式串重新开始匹配。
KMP算法实现如下：
int myStringIndexSubString(MyString *S,MyString *substr,int pos){ //KMP算法
int i = pos,j = 0;
if(!S || !substr || pos > S->length) return -1;
int *nextval = getKMPNext(substr);
if(!nextval) return -1;
while(i < S->length && j < substr->length){
if(*(S->str + i) == *(substr->str + j)){
i++;
j++;
}else{
j = *(nextval+j); //i不需要回溯，j回到指定位置
if(j == -1){
i++; //当j为-1时，要移动的是i
j++; //j归0
}
}
}
free(nextval);
if(j == substr->length){
return i - j;
}else{
return -1;
}
}
KMP的算法是在已知模式串的next函数值的基础上执行的，那么，如何求得模式串的next函数值是很重要的。
从上述讨论可见，此函数值仅取决于模式串本身而和相匹配的主串无关。我们可以从分析其定义出发用递推的方法求得next函数值。
先来看第一个：当j为0时，如果这时候不匹配，怎么办？
当j为0时就不匹配
像上图这种情况，j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next[0] = -1这个初始化。如果是当j为1的时候呢？
当j为1的时候不匹配
显然，j指针一定是后移到0位置的。因为它前面也就只有这一个位置了，next[1] =0。
当{0<k<j且“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”}集合不空时，设next[j] = k,这表明在模式串中存在下列关系：
“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”，其中k为满足0<k<j的某个值，并且不可能存在k'>k满足前面的等式。
此时next[j+1] =？可能有两种情况：
1.p[k] = p[j],如下图所示：
p[k] = p[j]
前面next[j] = k时，已经存在“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”这一等式，若p[k] = p[j]，则很容易的得出：
“p0 p1 ... pk” = “pj-k pj-k+1 ... pj”，
即在此基础上两边加上相等的p[k]、 p[j]，
则next[j+1] = k+1，即next[j+1]=next[j] +1。
2.p[k] != p[j]，如下图所示：
p[k] != p[j]
此时“p0 p1 ... pk” != “pj-k pj-k+1 ... pj”，可以把求next函数值的问题看成是一个模式匹配的问题，整个模式串既是主串又是模式串，而当前在匹配过程中，已有“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”这一等式，则当p[k] != p[j]时应将模式串向右滑动至以模式串中的第next[k]个字符和主串中的第j个字符相比较，如下图所示：
第next[k]个字符和主串中的第j个字符相比较
这就是为什么代码中为k = *(nextval+k)
当其他情况时，next[j] =0，这表明模式串从头开始比较。
getKMPNext函数
static int *getKMPNext(MyString *substr){
int *nextval = (int *)malloc((substr->length)*sizeof(int));
int j=0,k=-1;
if(nextval){
*nextval = -1;
while(j<substr->length){
if(k == -1 || *(substr->str+j) == *(substr->str+k)){
if(*(substr->str+(++j)) == *(substr->str+(++k))){ //两个字符相等时跳过
*(nextval+j) = *(nextval+k);
}else{
*(nextval+j) = k;
}
}else{
k = *(nextval+k);
}
}
return nextval;
}else{
return NULL;
}
}
在上面的getKMPNext函数中还修正了next的值。前面定义的Next表达式有一个小缺陷，看一个例子：
例子
显然，根据Next表达式得到的next数组应该是[ -1，0，0，1 ]，所以下一步我们应该是把j移动到第1个元素：
把j移动到第1个元素
不难发现，这一步是完全没有意义的。因为后面的B已经不匹配了，那前面的B也一定是不匹配的，同样的情况其实还发生在第2个元素A上。
发生问题的原因在于P[j] == P[next[j]]。
所以在getKMPNext函数中添加一个判断条件：
if(*(substr->str+(++j)) == *(substr->str+(++k))){ //两个字符相等时跳过
修正后的next数组是[ -1，0，0，0 ]。
getKMPNext函数的时间复杂度为O(m)。通常，模式串的长度m比主串的长度n要小的多，因此，对整个匹配算法来说，所增加的这点时间是值得的。
最前面介绍的匹配算法的时间复杂度是O(n*m),但在一般情况下，其实际的执行时间近似于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下才显得比这个算法快得多。但是KMP算法的最大特点是指示主串的指针不需要回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。
KMP算法的实现基于之前的C封装字符串、字符串数组对象内容：C封装字符串、字符串数组对象
testMyString.c文件：
#include <stdio.h>
#include <malloc.h>
#include "MyString.h"
int printMyString(MyString *str){
printf("%s, ",str->str);
printf("length :%d\n",str->length);
return 0;
}
int printMyStringElem(MyString **str){
printf("%s ",(*str)->str);
return 0;
}
int main(void){
int i;
char words[] = {"without new experiences, something inside of us sleeps."};
MyString *str_a = NULL;
MyString *str_b = NULL;
MyString *str_c = NULL;
MyStringArray *str_array = NULL;
str_a = myStringAssign("hello ");
str_c = myStringAssign("hello ");
printf("str_a :");
printMyString(str_a);
printf("is MyString empty: %d\n",isMyStringEmpty(str_a));
if(compareMyString(str_a,str_c)==0){
printf("str_a equals str_c\n");
}else{
printf("str_a is not equal str_c\n");
}
clearMyString(str_a);
printf("is MyString empty: %d\n",isMyStringEmpty(str_a));
if(compareMyString(str_a,str_c)==0){
printf("str_a equals str_c\n");
}else{
printf("str_a is not equal str_c\n");
}
destroyMyString(str_a);
str_a = copyMyString(str_c);
str_b = myStringAssign("Mr Bluyee");
printf("str_b :");
printMyString(str_b);
destroyMyString(str_c);
str_c = concatMyString(str_a,str_b);
printf("str_c :");
printMyString(str_c);
printf("the MyString : Mr Bluyee index: ");
i = myStringIndexSubString(str_c,str_b,0);
printf("%d\n", i);
printf("the char \'B\' index: %d\n", myStringIndexChar(str_c,'B',0));
insertMyString(str_a,str_b,str_a->length);
printf("str_a :");
printMyString(str_a);
destroyMyString(str_c);
str_c = substrMyString(str_a,0,5);
printf("str_c :");
printMyString(str_c);
destroyMyString(str_c);
str_c = myStringAssign(words);
str_array = splitMyString(str_c,' ');
str_array->traverse(str_array,printMyStringElem);
destroyMyString(str_a);
destroyMyString(str_b);
destroyMyString(str_c);
DestroyMyStringArray(str_array);
return 0;
}
KMP匹配的调用的代码段是：
printf("the MyString : Mr Bluyee index: ");
i = myStringIndexSubString(str_c,str_b,0);
printf("%d\n", i);
编译：
gcc MyString.c MyString.h MyStringArray.c MyStringArray.h testMyString.c -o testMyString
运行testMyString：
str_a :hello , length :6
is MyString empty: 0
str_a equals str_c
is MyString empty: 1
str_a is not equal str_c
str_b :Mr Bluyee, length :9
str_c :hello Mr Bluyee, length :15
the MyString : Mr Bluyee index: 6
the char 'B' index: 9
str_a :hello Mr Bluyee, length :15
str_c :hello, length :5
without new experiences, something inside of us sleeps.
本篇文章部分内容整理自：（原创）详解KMP算法
网友评论