目的:判断目标串(T串)中是否含有模式串(P串)。
失配
T t0 t1 t2 …… tk tk+1
P p0 p1 p2 …… pk
由于字符串T和P第一个不相等的字符出现在位置k,所以两字符前k个字符是相等的,也说明两串在位置k处失配。
失效函数
定义:记录字符串P中各个字符之间关系的函数。
定义域:自变量 j 的取值范围是P在“失配”前匹配的字符个数,定义域为0~len(P)-1(len(P)为P的字符串长度)。
例如:P = caatcat,失效函数的定义域为 j ∈ {0,1,2,3,4,5,6}。
值域:k ∈ {x | 0 ≤ x <j },且k为满足p0p1…pk = pj-k pj-k+1…pj的最大正整数。
若k不存在,则失效函数的取值为-1。
例:以 P = caatcat 的失效函数为例作表。
j = 0:0 ≤ k<0,k不存在,f(0) = -1;
j = 1:0 ≤ k<1,k = 0, p0 ≠ p1(‘c’ ≠ ‘a’),k不满足条件故不存在,f(1) = -1;
j = 2:k = 0、1,p0 ≠ p2且p0 p1 ≠ p1p2,k不满足条件故不存在,f(2) = -1;
j = 3:k = 0、1、2,p0 ≠ p3且p0 p1 ≠ p2p3且p0 p1p2 ≠ p1p2p3,k不满足条件故不存在,f(3) = -1;
j = 4:k = 0、1、2、3,p0 = p4且p0 p1 ≠ p3p4且p0 p1p2 ≠ p2p3p4且p0 p1p2p3 ≠ p1p2p3p4,k=0满足条件,f(4) = 0;
j = 5:k = 0、1、2、3、4,p0 ≠ p5且p0 p1 = p4p5且p0p1p2≠ p3p4p5且p0p1p2p3≠ p2p3p4p5以及p0p1p2p3p4 ≠ p1p2p3p4p5,k = 1满足条件,f(5) = 1;
同理可求f(6) = -1;
失效函数:
失配函数 f (j) 仅与模式P有关,与目标T无关,所以只要是同一个P,失效函数就适用。
mp匹配
长串在短串某个字符匹配成功时向前移动一个位置
失配情况发生在模式P的第j位
: j = 0: 让目标T的指针前进一位,模式P的起始比较地址为p0
: j ≠ 0: 目标T的指针不发生回溯,仍指向失配的位置,模式P的起始比较地址为P[f(j-1)+1]
mp算法是时间复杂度为O(m+n)[^1]
[^1]: P字符串的长度为m,T字符串长度为n
#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; void preMP(const char* x, int m, int mpNext[]) { int i, j; i = 0; j = mpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = mpNext[j]; mpNext[++i] = ++j;//mpNext(j)=f(j-1)+1 } } void MP(string p, string t) { int m = p.length(); int n = t.length(); //模式串长度大于目标串即找不到 if (m > n) { cout << "unsuccessful match!" << endl; return; } /*c_str()用法:将string转换为c的字符串类型 详解:https://blog.csdn.net/qq_29493173/article/details/100043142 */ const char* x = p.c_str(); const char* y = t.c_str(); //i是模式串P的指针位置 j是目标串T的指针位置 int i = 0, j = 0; /*mpNext[]存储的是失配发生时,下一轮P的起始比较地址; 因为存储的是P,数组大小比P长度略大即可*/ int mpNext[m+1]; //为mpNext[]赋值 preMP(x, m, mpNext); //T的指针没到末尾就一直寻找 while (j < n) { //指针指向位置的元素不同,且不为P首元素,P的指针将指向下一个索引位置 while (i > -1 && x[i] != y[j]) i = mpNext[i]; //若两指针指向元素相同,一齐往后移动1 i++; j++; //找到完整P串输出index if (i >= m) { cout << "index at:" << j-i << endl; i = mpNext[i];//可继续找下一个P串的index } } } int main() { fio string t = "ctcaatcacaatcat"; string p = "caatcat"; MP(p, t); }
KMP
KMP算法与MP非常相像,用kmpNext[ ]表对P中符合要求的加标边际进行标识。
u表示P、T匹配相同的一段子串,v表示失配移动后匹配到子串u的某一部分后缀,i处的“a”与j+i处的“b”失配。
符合要求:(简单来说就是对MP的移动进一步筛选处理)
①偏移后的v是可以匹配到u中某个后缀的一个最长前缀。
②v后面的字符c和u后面的字符a不同(因为a与b失配)
kmpNext表的建立可以在mpNext表的基础之上,分为四种情况,其中1 ≤ j ≤ m-1:
1.如果mpNext[j] = 0 且 pj = p0,则令kmpNext[j] = -1;
2.如果mpNext[j] = 0 且 pj ≠ p0,则令kmpNext[j] = 0;
3.如果mpNext[j] ≠ 0 且 pj ≠ pmpNext[j],则令kmpNext[j] = mpNext[j];
4.如果mpNext[j] ≠ 0 且 pj = pmpNext[j],则令 j 替换成mpNext[j],直到情况转换为前三种,进而递归求解kmpNext[j];
仍以caatcat为例求出kmpNext表:
KMP模板
#include<bits/stdc++.h> #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; void preKMP(const char* x, int m, int kmpNext[]) { int i = 0, j; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; /*与mp不同的地方*/ if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j; } } void kmp(string p, string t) { int n = t.length(); int m = p.length(); if (m > n) { cout << "find unsuccesfully"<< endl; return; } //i短串,j长串 int i = 0, j = 0, kmpNext[m+1]; const char* x = p.c_str(); const char* y = t.c_str(); preKMP(x, m, kmpNext); while (j < n) { while (i > -1 && x[i] != y[j]) i = kmpNext[i]; i++; j++; if (i >= m) { cout << "index at:" << j-i << endl; i = kmpNext[i]; } } } int main() { fio string t = "ctcaatcacaatcat"; string p = "caatcat"; kmp(p, t); }