这是一个改进的字符串匹配算法,提供更快的关键词搜索功能。介绍这个可以从分析我们肉眼查找关键词时的做法做起。
这儿有一个串串,假设我们要找到关键词abababca,就是下面那一行玩意
ABABABABCA
ABABABCA
经过观察发现,在匹配位置(标红)出问题前一共有6个字符匹配成功,这六个字符组成的字符串在原串和模式串中是一样的 而且这个串“ABABAB”有一个特点,它的前4个字符和后4个字符是一样的,因此下一次匹配的时候,可以略去前四个字符(标蓝)直接从第五位开始匹配
也就是说,下一次匹配初始位置 = 重复串长度值 + 1 (注意,原串中匹配位置不会发生变化)
ABABABABCA
ABABABCA
可以发现,如果知道在某字符失配前吻合的字符串中,首尾有多长的部分是重复的,那就可以节约大量的匹配时间 更快加入游戏
针对这个问题,可以建立一个一维数组来存储,以在匹配时直接读取数据。扫描思路很简单,每次错开一位和自己匹配,匹配成功多长就是重复了多少位。具体过程参考下头的图:其中next数组存储 “最长相等的前缀和后缀子串”
应该注意到了next的元素编号似乎后移了一位吧?回头看看绿字就能理解了。为了方便起见,next数组的首位即next[0]手动设置为为-1,表示第一位就失去同步的情况。这样在匹配的时候,只要在某一位出现不匹配,将这个值代入next[]就可以知道下一次匹配从第几位开始。
下面贴出我在参考了一些其他代码后写出的拙劣代码,用以实现对给出的关键词串求出next数组:
void Ne_xt(char* msc, int* next)
{
int i = 0, j = -1;
next[0] = -1;
while( i < strlen(msc) )
{ if( msc[i] == msc[j] || j == -1 )
{ i++; j++; next[i]=j; }
else
{ j=next[j]; }
/*注意这事实上已经应用了KMP算法的思路进行自我匹配,j的位置就是失配点前的位置,next[j]即是获取从开头算起有多少重复的字符,而
由于数组从0开始标号,next[j]本身能够代表重复部分的下一位即第(j+1)个字符的情况。 */
}
}
在得到了next数组之后,算法的关键已经解决。接下来编写另一程序实现KMP算法,在实际使用时会调用Ne_xt函数。
int KMP(char* A, char* B)
//输入两个字符串指针,返回首字符位置,-1为不存在
{
int i=0, j=0;
int next[strlen(B)];
Ne_xt(B,next);
while( i<strlen(A) && j<strlen(B) )
{
if( A[i] == B[j] || j == -1 )
{ i++; j++; }
else
{ j = next[j]; }
}
if( j == strlen(B) )
return i-j; //成功返回目标首字符位置
else
return -1; //失败返回-1
}