c++kmp算法字符匹配_数据结构基础串模式匹配算法KMP

改进的模式匹配算法(KMP)&＃xff1a;

改进之处在于&＃xff0c;当匹配过程中出现相比较的字符不相等时&＃xff0c;不需要回退主串的字符位置指针&＃xff0c;而是利用已经得到的“部分匹配”的字符&＃xff0c;将模式串向右滑动尽可能远的距离&＃xff0c;再进行比较。具体向右滑动多少距离&＃xff0c;就得依据next函数值进行计算。依据模式串next函数值整理的表&＃xff0c;就叫《部分匹配表》。

滑动距离&＃61;已“部分匹配”的字符数-next函数值。

部分匹配表如何产生&＃xff1a;

• 1.第一种方式&＃xff1a;

“前缀”&＃xff1a;除了最后一个字符外&＃xff0c;一个字符串的全部头部组合。

“后缀”&＃xff1a;除了第一个字符外&＃xff0c;一个字符串的全部尾部组合。

“部分匹配值“&＃xff1a;指前缀和后缀的最长共有元素的长度。也就是next函数值。

部分匹配表&＃xff0c;就是根据部分匹配值(next函数值)整理得出。

如果模式串为abababb&＃xff0c;则部分匹配表如下所示&＃xff1a;

部分匹配表

我们定义下标0为字符串的开始&＃xff0c;规定next[0]&＃61;-1;

j&＃61;1时&＃xff0c;前面字符串a&＃xff0c;前缀和后缀都为空集&＃xff0c;共有元素最长长度为0&＃xff1b;

j&＃61;2时&＃xff0c;前面字符串ab&＃xff0c;前缀为【a】,后缀为【b】,没有共有元素&＃xff0c;共有元素最长长度为0;

j&＃61;3时&＃xff0c;前面字符串aba&＃xff0c;前缀为【a】【ab】,后缀为【a】【ba】,共有元素最长长度为1;

j&＃61;4时&＃xff0c;前面字符串abab&＃xff0c;前缀为【a】【ab】【aba】,后缀为【b】【ab】【bab】,共有元素最长长度为2;

j&＃61;5时&＃xff0c;前面字符串ababa&＃xff0c;前缀为【a】【ab】【aba】【abab】,后缀为【a】【ba】【aba】【baba】,共有元素最长长度为3;

j&＃61;6时&＃xff0c;前面字符串ababab&＃xff0c;前缀为【a】【ab】【aba】【abab】【ababa】,后缀为【b】【ab】【bab】【abab】【babab】,共有元素最长长度为4;

• 2.第二种方式

next函数定义如下&＃xff1a;

&＃xfeff;next函数

如果模式串为abababb&＃xff0c;根据next函数&＃xff1a;

当j&＃61;0时&＃xff0c;next[0]&＃61;-1。

当j&＃61;1时&＃xff0c;因0

当j&＃61;2时&＃xff0c;0

当j&＃61;3时&＃xff0c;0

当j&＃61;4时&＃xff0c;0

当j&＃61;5时&＃xff0c;0

依次计算&＃xff0c;就可以得到如图部分匹配表中的结果。

next函数推导过程如下&＃xff1a;

我们定义串中的位置指针分别为i(主串指针)和j(模式串指针),第一个位置以下标0开始&＃xff0c;如下图所示&＃xff1a;

根据KMP基本思想&＃xff0c;当匹配到C和B不相等时&＃xff0c;指针需要移动一定的距离&＃xff0c;通过看上图我们发现&＃xff0c;j需要移动到第二个位置&＃xff0c;即C处&＃xff0c;如下图所示的位置&＃xff1a;

我们设匹配失败时&＃xff0c;j要移动的下一个位置为k,此时k移动的位置只能在0到k之间&＃xff0c;即0

定义主串字符组为T,模式串字符组为P。

如上图所示&＃xff0c;此时我们发现0

当T[i] !&＃61; P[j]时

由T[i-j ~ i-1] &＃61; P[0~j-1]

由P[0 ~ k-1] &＃61;&＃61; P[j-k ~ j-1]

必然&＃xff1a;T[i-k ~ i-1] &＃61;&＃61; P[0 ~ k-1]

next函数