子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的操作之一，例如很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。子串定位算法即称为模式匹配算法。
上面的next数组我会在下面详细介绍怎么来的，你也可以自己去推。现在只需要知道有这么个东西，怎么在KMP算法里面用它就可以了。下面我会贴出代码，你可以推理过程，代码一起看，这样容易理解。[cpp] view plain copyvoid KMP(HString *s,HString *t) {<span> </span>//s是主串，t是模式串 int i=0, j=1; while (i < s->length && j <= t->length) { //只要i,j小于各自串的长度，说明它们还没有匹配完 if (j == 0 || s->str[i] == t->str[j - 1]) { i++; j++; //如果j==0，说明该位置字符与模式串首字符失配，都自增一。 } //第二个条件满足，说明对应位置字符相同，继续比较后继字符 else j = nextNum[j]; //否则模式串移动相应的个数 } if (j>t->length) { cout << "子串的位置为： " << i - t->length + 1 << endl; } else { cout << "没有该子串！" << endl; } } 这里需要注意，nextNum[]就是next数组，因为命名冲突，所以没有直接起。字符数组是从0开始的，而nextNum[ ]是从1开始的，nextNum[0]并没有使用。
知道怎么用了，我们再讲讲原理。模式串字符的排列我们是已知的，但是如何去利用它呢？在这种具有重复字符的模式串里面，我们总能找到相同的部分。比如上图第三趟匹配到第四趟匹配过程中，他们的相同部分是a b。
有相同部分再进行匹配是不是比失配就回溯节约时间。现在关键来了，我们都是利用模式串预先计算出来的next数组来实现的，那我们怎么来计算next数组里面的值呢？我先贴出代码：[cpp] view plain copyvoid Next(HString *t) { int i = 1, j = 0; nextNum[1] = 0; while (i<t->length) { if (j == 0 || t->str[i - 1] == t->str[j - 1]) { ++i; ++j; nextNum[i] = j;<span> </span> } else { j = nextNum[j];<span> </span>//回溯，在新的子串里面查找新的最大相同子串 } } } 在这个算法里面所求得的nextNum数组，nextNum[1]=0,nextNum[2]=1,这是默认的。很显然，当模式串第一个字符都失配，我不能让模式串去移动下一位，那只能主串匹配位置自增一，继续匹配。当模式串第二个字符失配时，那只能看第一个字符能否匹配，如果可以，继续匹配后继字符；不能，那主串匹配位置自增一。核心就是从next数组的第三位值开始，值得大小取决于之前的字符从首尾开始组成最大的相同子串的长度，如果找到，那么next值是该长度加1，否则next值是1。例如 : 模式串 a b a a b c nextNum[] 0 1 1 2 2 3 1)第二个字符失配也可以这么理解，字符组合：{0 | a} 最大相同子串为空,nextNum[2]=0+1;2)第三个字符, 字符组合 {0,a| b,0}. 最大相同子串为空，nextNum[3]=0+1;3)第四个字符，字符组合 {0,a,ab | ba,a,0}. 最大相同子串为a，长度为1，nextNum[4]=1+1;5)第五个字符，字符组合 {0,a,ab,aba | baa,aa,a,0}. 最大相同子串为a，长度为1，nextNum[5]=1+1;6)第六个字符，字符组合{0,a,ab,aba,abaa|baab,aab,ab,a,0}最大相同子串为ab，长度为2，nextNum[6]=2+1;花括号前半部分是除尾字符的所有子串字符组合，后半部分是除首字符的所有子串组合。KMP完整代码：[cpp] view plain copy#include<iostream> using namespace std; #define max 100 int nextNum[max]; typedef struct { int length; char *str; }HString; void Next(HString *t) { int i = 1, j = 0; nextNum[1] = 0; while (i<t->length) { if (j == 0 || t->str[i - 1] == t->str[j - 1]) { ++i; ++j; nextNum[i] = j; } else { j = nextNum[j]; } } } void KMP(HString *s,HString *t) { int i=0, j=1; while (i < s->length && j <= t->length) { //只要i,j小于各自串的长度，说明它们还没有匹配完 if (j == 0 || s->str[i] == t->str[j - 1]) { i++; j++; //如果j==0，说明该位置字符与模式串首字符失配，都自增一。 } //第二个条件满足，说明对应位置字符相同，继续比较后继字符 else j = nextNum[j]; //否则模式串移动相应的个数 } if (j>t->length) { cout << "子串的位置为： " << i - t->length + 1 << endl; } else { cout << "没有该子串！" << endl; } } void main() { HString s1,s2; s1.length = 17; s1.str = (char*)malloc(sizeof(char)); s1.str = "acabaabaabcacaabc"; s2.length = 6; s2.str = (char*)malloc(sizeof(char)); s2.str = "adacba"; Next(&s2); KMP(&s1, &s2); for (int i = 1; i < 7; i++) { cout << nextNum[i]; } system("pause"); } 新闻热点
疑难解答
