数算---字符串匹配（BF、RK、KMP算法）
前言
本文将从下面题目出发，分别介绍三种字符串匹配的方法。
题目
有一个主串S = {a , b, c, a, c, a, b, d}，模式串T= {a, b, d} ,请找到模式串在主串第一次出现的位置。（均为小写字母）
字符串匹配
1、BF算法
这种方法比较暴力，直接从头至尾一个字符一个字符移动，然后进行相应位置的字符比较，相应位置都相等的话那么就找到了，只要有一个位置不想等，那就向右移动一个字符，再一次循环比较相应位置字符。看起来比较直接，比较暴力。
思路分析
1.分别利用指针 i 和 j 指示主串S和模式T中当前正在等待比较的字符位置，i默认为pos，j初值为1。
2.两个串都还未比较到结尾时，即i 和 j 小于等于S和T的长度，循环一下操作：
- S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
- 若不相等,指针后退重新开始匹配. 从主串的下一个字符串
(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
3.如果j > T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0;
代码
#define MAXSIZE 40
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
int Index_BF(String S, String T,int pos){
//i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配
int i = pos;
//j用于子串T中当前位置下标值
int j = 1;
//若i小于S的长度并且j小于T的长度时，循环继续
while (i <= S[0] && j <= T[0]) {
//比较的2个字母相等,则继续比较
if (S[i] == T[j]) {
i++;
j++;
}else
{
//不相等,则指针后退重新匹配
//i 退回到上次匹配的首位的下一位;
//加1,因为是子串的首位是1开始计算;
//再加1的元素,从上次匹配的首位的下一位;
i = i-j+2;
//j 退回到子串T的首位
j = 1;
}}
//如果j>T[0],则找到了匹配模式
if (j > T[0]) {
//i母串遍历的位置 - 模式字符串长度 = index 位置
return i - T[0];
}else{
return -1;
}
}
//测试代码
int i;
String s1,s2;
StrAssign(s1, "abcdex");
printf("s1子串为");
StrAssign(s2, "xe");
printf("s2子串为");
i = Index_BF(s1, s2, 1);
printf("i = %d\n",i);
在某些情况下上面BF算法的效率太低，如下图所示：
BF算法弊端
可见，当T在第41个位置时终于匹配成功，期间进行了
（50 - 10 + 1）* 10次判断操作。接下来我们将介绍RK算法，看看它的效率又如何呢？
2、RK算法
RK算法的核心思想是如何将模式串或者主串拆分后的子串换算成一个哈希值。因为相同字符串哈希值相等，所以可以将子串的哈希值比较，从而减少运算量。
所以字符串匹配核心思想就是将字母换算成哈希值。
将 ‘当前字母’ - ‘a‘ = 数字
例如：
a - a = 0;
b - a = 1;
c - a = 2;
d - a = 3;
.............
就像数字之间存在8进制，10进制一样，字母之间也存在进制。
256 = 2 * 10 * 10 + 5 * 10 + 6 * 1
567 = 5 * 10^2 + 6 * 10^1 + 7 * 10^0
字母之间的进制那就是26进制，我们可以根据这个制定一个哈希值算法：
cba = 'c' * 26 * 26 + 'b' * 26 + 'a' * 1 = c x 26^2 + b x 26^1 + a x 26^0
cba = 2 * 26 * 26 + 1 * 26 + 0 * 1 = 2 x 26^2 + 1 x 26^1 + 0 x 26^0
cba = 1378 （1378 即为cba在当前算法下的哈希值）
由此，我们可以先假设主串为 { d , b , c, e, d , b }，模式串为 {c, c, c}，按三个一组通过上面的26进制来计算主串中的子串的哈希值：
字串26进制
图中所示，相邻两个子串对应的哈希值计算公式有交集，也就是说我们可以使用s[i - 1] 计算出s[i] 的哈希值。
我们可以先借助数字串来帮助我们更好地理解：
数字全集： {0, 1 , 2 ,3 , 4, 5, 6, 7, 8, 9} ，则为10进制，模式串为123，主串为 65127451234.
主串所有子串
我们拿 第三位置的127 和第四位置的274 来比较:
s[ i ] = 1 x 10^2 + 2 x 10^1 + 7 x 10^0
s[ i + 1 ] = 2 x 10^2 + 7 x 10^1 + 4 x 10^0
s[i + 1] = 10 x (127 - 1 x 10^2) + 4
s[i + 1] = 10 x (s[i] - 1 x 10^2) + 4
s[i + 1]实际就是上一个s[ i ] 去掉最高位1 x 10^2 ，剩余后面两位 之和再加上 4 x 10^0 即 4 x 1 = 4。
综上所述，当模式串长度 m = 3，d 为进制10，主串从i = 1，首个数字开始与模式串比较，前后相邻两个子串关系为：
st[i + 1] = (st[ i ] - s[i] x d^(m - 1)) x d + s[i + m]
同理，字符串也可以按同样的规律计算相邻子串的哈希值公式：
字符串哈希值公式
利用以上公式得到每个子串的哈希值，即可将所有子串与模式串比较，相等则找出结果，不过还需要考虑哈希冲突（字串与模式串哈希值相等，但是字符串不相同），那么就需要更复杂的哈希算法。当发现冲突时，需要二次确认2个字符串是否相等。
代码实现
//设置 26 进制
#define d 26
//二次比较，排查哈希冲突
int isMatch(char *S, int i, char *P, int m)
{
int is, ip;
for(is=i, ip=0; is != m && ip != m; is++, ip++)
if(S[is] != P[ip])
return 0;
return 1;
}
//算出 d^(m - 1) 的值
int getMaxValue(int m){
int h = 1;
for(int i = 0;i < m - 1;i++){
h = (h*d);
}
return h;
}
//// S 主串 P 模式串
int RK(char *S, char *P)
{
//1. n:主串长度, m:子串长度
int m = (int) strlen(P);
int n = (int) strlen(S);
printf("主串长度为:%d,子串长度为:%d\n",n,m);
//A.模式串的哈希值; St.主串分解子串的哈希值;
unsigned int A = 0;
unsigned int St = 0;
//2.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]
//循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
//此时主串:"abcaadddabceeffccdd" 它的[0,2)是ab
//此时模式串:"cc"
//cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;
//ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;
for(int i = 0; i != m; i++){
//第一次 A = 0*26+2;
//第二次 A = 2*26+2;
A = (d*A + (P[i] - 'a'));
//第一次 st = 0*26+0
//第二次 st = 0*26+1
St = (d*St + (S[i] - 'a'));
}
//3. 获取d^m-1值(因为经常要用d^m-1进制值)
int hValue = getMaxValue(m);
//4.遍历[0,n-m], 判断模式串HashValue A是否和其他子串的HashValue 一致.
//不一致则继续求得下一个HashValue
//如果一致则进行二次确认判断,2个字符串是否真正相等.反正哈希值冲突导致错误
//注意细节:
//① 在进入循环时,就已经得到子串的哈希值以及主串的[0,m)的哈希值,可以直接进行第一轮比较;
//② 哈希值相等后,再次用字符串进行比较.防止哈希值冲突;
//③ 如果不相等,利用在循环之前已经计算好的st[0] 来计算后面的st[1];
//④ 在对比过程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]来求解s[i+1] . 简单说就是一边比较哈希值,一边计算哈希值;
for(int i = 0; i <= n-m; i++){
if(A == St)
if(isMatch(S,i,P,m))
//加1原因,从1开始数
return i+1;
St = ((St - hValue*(S[i]-'a'))*d + (S[i+m]-'a'));
}
return -1;
}
//测试代码
char *buf="abcababcabx";
char *ptrn="abcabx";
printf("主串为%s\n",buf);
printf("子串为%s\n",ptrn);
int index = RK(buf, ptrn);
printf("find index : %d\n",index);
RK算法就是一边比较哈希值,一边计算哈希值，在计算量上没有BF算法多，可能理解上稍微有点绕。
3、KMP算法
由于BF算法需要进行比较的次数是最多，从前往后移动每次比较都需要从模式串的第一个字符开始比较。那么有没有更多能减少比较次数的方法？下面将从几种不同的模式串着手来分析KMP算法的优势。
情况一
当模式串中所以字符两两比较都不一样时：
模式串无重复字符
在这个例子中，如果按BF算法计算，那么每次都需要 j = 6 时才知道不匹配。也就是主串从左往右遍历，每次都需要从模式串的第一个开始比较，但明显 a 与 模式串其余字符都不相同，那么在i为[1 , 5]范围内都没必要再比较，可以直接从i = 6继续遍历比较。
情况二
当模式串中有相同字符时，例如：
模式串有重复字符
由左向右遍历，当 i 为[1, 4]范围内，模式串比较下标 j 都需要从 1 ，即 j = 1；当i = 5 时，由于S[4] = T[1]，那么此时就可以从j = 2开始比较，发现S[5] = T[2] ; 同理当 i = 6 时，由于 S[4] = T[1] 和 S[5] = T[2]，所以S[6] 可以直接和 T[3] 进行比较，也就是 i = 6 时，j = 3，这样也就减少了比较的次数。
综上所述，我们可以把T串各个位置j值变化定义为一个 next 数组，那么next就是长度就是T串的长度：
next与j的关系
所以情况一中的 T = abcdex ，所对应的next[j] = 011111，那这是怎么得来的呢？
- 当 j=1时, next[1] = 0
- 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
- 当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1;
- 当 j=4时, j 由 1到 j-1 范围内有字符”abc”,显然abc 不存在相等情况,则属于其他情况 next[4] = 1;
- 当 j=5时, j 由 1到 j-1 范围内有字符”abcd”,显然abcd 不存在相等情况,则属于其他情况 next[5] = 1;
-
当 j=6时, j 由 1到 j-1 范围内有字符”abcde”,显然abcde 不存在相等情况,则属于其他情况 next[6] = 1;
同理，情况二中的 T = abcabx， 所对应的next[j] = 011123：
- 当 j=1时, next[1] = 0
- 当 j=2时, j 由 1到 j-1 范围内只有字符 “a”, 属于其他情况 next[2] = 1;
- 当 j=3时, j 由 1到 j-1 范围内有字符 “ab”,显然 a 不等于 b, 属于其他情况 next[3] = 1;
- 当 j=4时, j 由 1到 j-1 范围内有字符”abc”,显然abc 不存在相等情况,则属于其他情况 next[4] = 1;
- 当 j=5时, j 由 1到 j-1 范围内有字符”abca”,显然 abca 前缀字符 “a” 与 后缀字符 “a” 相等 ; (由于 ’p1…pk-1’ = ‘ pj-k+1 … pj-1’,得到p1 = p4) 因此可以推算出 k 值为2; 因此 next[5] = 2;
- 当 j=6时, j 由 1到 j-1 范围内有字符”abcab”,显然 abcab 前缀字符 “ab” 与 后缀字符 “ab” 相等; (由于 ’p1…pk-1’ = ‘ pj-k+1 … pj-1’,得到 [p1, p3-1] = [p6-3+1,p5] ) 推导 k 值为 3, 因此next[6] = 3；
结论： 如果前后缀一个字符相等时k值是2，两个字符相等是3；那么n 个相等的k值就是n + 1。
我们可以多举几个例子：
T = {ababaaaba} ==> next[j] = [011234223]
其中相同的前后缀分别为 [ 空，空，空，a, ab , aba , a , a, ab]
空的意思就是 j 由 1 到 j - 1 范围内没有重复字符，需要从j = 1 从头比较。
T = {aaaaaaaab} ==> next[j] = [012345678]
其中相同的前后缀分别为 [ 空，空，a，aa, aaa , aaaa , aaaaa , aaaaaa, aaaaaaa]。
我们也可以进行下面的方法来证实上面的结论：
情况一的时候T= “abcdex” ， next[j] = 011111；
验证1
-
默认next[1] = 0；
-
i = 0, j = 1 开始遍历；
-
比较 T[ i ] != T[ j ] ， 但是 i = 0， 则表示 [0, 1]范围内 [a] 只能从1的位置开始；
-
j++,i++ ,所以 i = 1, j = 2;
-
更新next[j] = i; 则 next[2] = 1;
验证2
-
比较T[i] != T[j] 所以将i的位置 回退到a之后，那么i = next[i];则i = next[i] = next[1] = 0;
-
此时[0, 2]这个范围内是否存在相等字符出现；
-
那么由于 i = 0， 所以此时的 next[j] 还是从第1个位置上字符开始比较；
-
i++ ,j ++; next[j] = next[3] = 1;
验证3
-
比较[1, 3]内 是否存在相等字符出现；
-
T[i] != T[j]， 所以i 的位置回退；
-
i = next[i] = 0;此时 i = 0;
验证4
- 比较[0, 3]范围内 是否有相同符号出现；
- 因为 出现 i = 0， 所以字符串比较需要从头开始；i ++, j++; i= 1， 即= 4；
-
next[j] = i; next[4] = 1;
验证5
- 比较[1, 4] 范围内是否有相等字符出现；
-
那么 T[i] != T[j] ,所以 i = next[i] = next[1] = 0,回溯
验证6
- 比较[0, 4]范围内出现相同字符与否；
- 因为 i = 0， 所以字符串要从头开始，则i ++, j++, i = 1, j = 5;
- next[j] = i, next[5] = 1;
.........
直到最后j = 6， 模式串已经处理完毕，则退出循环。
同样的验证方式可以对T = “abcabx” 进行验证，可归纳为以下规律：
- 默认 next[1] = 0;
- i = 0, j = 1 开始遍历；
- 当 j < S.length j 从 1~length 遍历字符串；
- 如果当 i = 0， 表示[i , j] 这个范围内没有找到相同的字符，所以 i 要回溯到 1 的位置； 表示 next[j] = i;
- 如果当 T[i] = T[j] 相等，表示找到与其相同字符的位置，所以next[j] = i;
- 当以上两个条件都不满足的话，则将i 回溯到前面记录的next[i]的位置。
代码实现
//准备代码
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
//----字符串相关操作---
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* 令串长为零 */
return OK;
}
/* 输出字符串T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
/* 返回串的元素个数 */
int StrLength(String S)
{
return S[0];
}
//----KMP 模式匹配算法---
//1.通过计算返回子串T的next数组;
//注意字符串T[0]中是存储的字符串长度; 真正的字符内容从T[1]开始;
void get_next(String T,int *next){
int i,j;
j = 1;
i = 0;
next[1] = 0;
//abcdex
//遍历T模式串, 此时T[0]为模式串T的长度;
//printf("length = %d\n",T[0]);
while (j < T[0]) {
//printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//T[i] 表示后缀的单个字符;
//T[j] 表示前缀的单个字符;
++i;
++j;
next[j] = i;
//printf("next[%d]=%d\n",j,next[j]);
}else
{
//如果字符不相同,则i值回溯;
i = next[i];
}
}
}
//输出Next数组值
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
int count = 0;
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_next(T, next);
count = 0;
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
//这里回溯的是j ，所以当j = 0 是，需要i ++ , j ++ ;
//第一个字符不匹配时候 j 就回溯了，j = next[1] = 0,
if(j == 0 || S[i] == T[j]){
i++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];//就是 与 T[1] 对应的位置下标
}else{
return -1;
}
}
// 测试嗲吗
//KMP算法调用
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcdex");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Index_KMP方法的while中，我们可以设置一个主串，一个模式串走一下过程：
next数组 01111
主串 abccabcceabc
模式串 abcce
i = 1 j = 1 => S[1] = T[1] => i++ j++
i = 2 j = 2 => S[2] = T[2] => i++ j++
i = 3 j = 3 => S[3] = T[3] => i++ j++
i = 4 j = 4 => S[4] = T[4] => i++ j++
i = 5 j = 5 => S[5] != T[5] => j = next[5] = 1
i = 6 j = 2 => S[6] = T[1] => i++ j++
i = 7 j = 3 => S[7] = T[2] => i++ j++
i = 8 j = 4 => S[8] = T[3] => i++ j++
i = 9 j = 5 => S[9] = T[4] => i++ j++
i = 10 j = 6 > T[0] = 5 结束
KMP优化
当然，KMP算法还有优化的空间。
例如主串 S = "aaaabcde" ,模式串 T ="aaaaax" . 数组next 为 012345 ;
当我们按上面的算法进行的话，还存在多余进行的步骤。
- 当i = 5, j = 5， S[5] != T[5]， 需要回溯，j = next[5] = 4;
- 当i = 5, j = 4， S[5] != T[4]， 需要回溯，j = next[4] = 3;
- 当i = 5, j = 3， S[5] != T[3]， 需要回溯，j = next[3] = 2;
- 当i = 5, j = 2， S[5] != T[2]， 需要回溯，j = next[2] = 1;
- 当i = 5, j = 1， S[5] != T[1]， 需要回溯，j = next[1] = 0;
- 此时i++, j++ ;i = 6, j = 1;
按上面的算法需要一步一步递减，直到 i = 5 , j = 1 ,继续对比。
其实，在比较过程中发现，这2, 3, 4, 5 步骤的回溯比较都是多余的判断。
由于T串第2 ，3 ，4，5 位置都是 ‘a’ ,那么可以用next[1] 的值取代后面几个next[j]的值。
则优化过的 nextVal = {0, 0, 0, 0, 0, 5}
同理：如果T = “ababaaaba” ,则 next= {011234223}, 优化过的nextVal = {010104210}。
- 当 j = 1, nextVal[1] = 0;
- 当 j = 2, 因为第二个字符“b” 的next值为1，而且第一个字符是"a",不想等，所以nextVal[2] = next[2] = 1;
- 当 j = 3，因为第3个字符“a” 的next值为1， 所以与第一位的"a"比较相等，所以nextVal[3] = nextVal[1] = 0;
- 当 j = 4, 因为第4个字符“b” 的next值为2， 所以与第二位的“b”比较相等，所以nextVal[4] = nextVal[2] = 1;
- 当 j = 5，next值为3， 第5位字符“a” 与第3位字符"a"相等，则nextVal[5] = nextVal[3] = 0;
- 当 j = 6，next值为4, 第6位字符“a”与第4位字符“b”不相等，所以nextVal[6] = 4;
.........
所以，可总结为以下规律：
- 默认nextVal[1] = 0;
- T[i] = T[j] 且 ++i, ++j 后 T[i] 依旧等于 T[j] 则 nextVal[i] = nextVal[j];
- i = 0，表示从头开始i ++, j++后， 且T[i] != T[j] 则 nextVal = j;
- T[i] == T[j]， 且 i++, j++后 T[i] != T[j], 则nextVal = j;
- 当T[ii] != T[j] 表示不相等，则需要将 i 退回到合理位置，则i = next[i];
void get_nextVal(String T,int *nextVal){
int i,j;
j = 1;
i = 0;
nextVal[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
++j;
++i;
//如果当前字符与前缀不同,则当前的j为nextVal 在i的位置的值
if(T[i] != T[j])
nextVal[j] = i;
else
//如果当前字符与前缀相同,则将前缀的nextVal 值赋值给nextVal 在i的位置
nextVal[j] = nextVal[i];
}else{
i = nextVal[i];
}
}
}
