【KMP算法】字符串匹配

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

一、问题

给定两个字符串S（原串)和(模式串)T，找出T在S中出现的位置。

二、朴素算法

当S[i] != T[j]时，把T往后移一位，回溯S的位置并重新开始比较。

(1) 成功匹配的部分(ABC)中，没有一样的字符

(a)

S: i	A	B	C	A	B	C	E
T: j	A	B	C	E

(b)

S: i	A	B	C	A	B	C	E
T: j		A	B	C	E

(c)

S: i	A	B	C	A	B	C	E
T: j			A	B	C	E

(d)

S: i	A	B	C	A	B	C	E
T: j				A	B	C	E

(2) 成功匹配的部分(ABA)中，有一样的部分(A)

(a)

S: i	A	B	A	A	B	A	C
T: j	A	B	A	C

(b)

S: i	A	B	A	A	B	A	C
T: j		A	B	A	C

(c)

S: i	A	B	A	A	B	A	C
T: j			A	B	A	C

(d)

S: i	A	B	A	A	B	A	C
T: j				A	B	A	C

三、KMP算法

基本思想：通过整理模式串T中的元素相似性，减少朴素算法中对原串S不必要的回溯。当发生失配时，回溯T到它的最长前缀的后一个位置，同时S的位置不变，再继续匹配。

前缀：包含T首字母的子串

后缀：包含T最后一个字母的子串

next数组

next[j]: 求得T[0, ..., j-1] 中最长的相同的前/后缀，next[j] 是该前缀的后一个字符所在位置。当T[j] 和S[i]不相同时，回溯T[j] 到next[j]，S[i]的位置不变。

(1) next[j] =-1 if j == 0 //第一个字符的回溯位置为 -1

(2) next[ j ] = max{ k |T₀...T_k-1 = T_j-k-1...T_j-1} //最长的相同的前后缀，回溯时相同的部分不用再比较

(3) next[j] = 0 if 其他情况 //没有找到相同的前后缀，回溯的时候只能从第一个字符重新开始比较

计算next数组

T中有两个相同的子串X(蓝色部分)，i 和 j 是当前比较的两个位置

(1) T[i] = T[j] = 2: next[j+1] = i+1 //T[0, ..., j] 的前缀Xi 和后缀Xj 一样

(2) 2 = T[i] != T[j] = 3: i = next[i] //对 i 进行回溯，重新寻找满足条件的前后缀。绿色部分，最后一个元素为 3

next数组的使用效果

(1) 成功匹配的部分(ABC)中，没有一样的字符 (省去 (b,c))

(a)

S: i	A	B	C	A	B	C	E
T: j	A	B	C	E
T: next[j]	-1	0	0	0

(d)

S: i	A	B	C	A	B	C	E
T: j				A	B	C	E
T: next[j]				-1	0	0	0

S[3] = D, T[3] = E，不相同。j = next[3] = 0 回溯。(ABC)没有相同的部分，因此不必将 S:i 回溯再尝试匹配。

(2) 成功匹配的部分(ABA)中，有一样的部分(A) (省去 (b))

(a)

S: i	A	B	A	A	B	A	C
T: j	A	B	A	C
T: next[j]	-1	0	0	1

(c)

S: i	A	B	A	A	B	A	C
T: j			A	B	A	C
T: next[j]			-1	0	0	1

(d)

S: i	A	B	A	A	B	A	C
T: j				A	B	A	C
T: next[j]				-1	0	0	1

S[3] = D, T[3] = C，第三个位置不匹配。j = next[3] = 1 回溯。下次比较是可以直接从S[3]和T[1]开始匹配，因为T[0] 和 T[2] 相同。

四、KMP算法源码

【hihocoder】 http://hihocoder.com/problemset/problem/1015?sid=808424

#include <iostream>
#include <string>
using namespace std; //计算next数组
void get_next(string& T, int* next)
{
int i = , j = -, Tlen = T.length();
next[] = -;
while(i < Tlen)
{
if(j == - || T[i] == T[j])
{
++i;
++j;
next[i]=(T[i] == T[j] ? next[j]:j);//使得回溯前和回溯后的元素不一样
}
else
j = next[j];
}
} //计算T在S中出现的次数
int subStrCnt(string& S, string& T)
{
int cnt = ;
int Slen = S.length(), Tlen = T.length();
int next[];
int i = , j = ;
get_next(T, next);
while(i < Slen && j < Tlen)
{
if(j == - || S[i] == T[j])
{
++i;
++j;
}
else
j = next[j];
if(j == Tlen){//T匹配完成，从T: next[j]再开始
cnt++;
j = next[j];
}
}
return cnt;
}
int main()
{
int cnt;
string S, T;
cin>>cnt;
while(cnt-- > )
{
cin>>T>>S;
cout<<subStrCnt(S, T)<<endl;
}
return ;
}