一、基本概念
两个字符串是否，其中一个是否在另一个中出现过呢，由此来进行探索
1.字符串匹配模式
字符串匹配模式是指一个字符串s中是否存在子串t，如果存在，返回t在s中的位置，否则返回-1
2.其他概念
前缀：以字符串的第一个字符为首字符的子串为字符串的前缀
后缀：以字符串的最后一个字符为尾字符的子串为字符串的后缀\
二、朴素模式匹配算法(BF算法)
从首字母一个个从进行比较，也许是最容易想到的一种方法
1.基本思想
从主串的第一个字符开始，依次判断以每一个字符作为起点的子串是否与模式串t匹配
2.算法1-1
功能：判断一个字符串t是否是主串s的子串
思路：
(1)定义一个变量k，表示每一轮主串的开始位置，当进入下一轮时，k增加1
(2)在每一轮的匹配中，定义两个变量i和j，初始值分别为k和0，进行这一轮的判断，如果s[i]=t[j]，则i和j同步增加，否则进入下一轮
(3)当j到达模式串的最后一个元素的下一个位置时，匹配成功
3.示例
当s=“ababcab”,t="abc"时，判断t是否是s的子串
#include<iostream>
using namespace std;
//朴素模式匹配算法，判断主串s中是否包含模式串t
int bf(string s, string t) {
int i = 0, j = 0, k = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) {
++i, ++j;//i，j同步后移
if (j == t.size())return k;//j到达模式串的最后一个字符的下一个位置，匹配成功
}
else {
++k, i = k, j = 0;
}
}
return -1;
}
int main() {
string s = "ababcab", t = "abc";
cout << bf(s, t) << endl;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
三、KMP算法
对于BF算法，t字符串不停的回退到开头的位置非常的浪费效率，因为t字符串很可能自身就存在重复，所以如果能够根据t字符串自身重复的情况进行不同程度回退，就可以提高效率
1.回退数组
1.含义
在进行模式匹配的时候，当s[i]!=t[j]的时候，只需要将j回退到适当的位置即可，假设移动到next[j]，next数组是由模式串决定的，值为模式串t的子串t[0,j-2]的前缀与子串t[1,j-1]的后缀相同的子串的最大长度，即
n
e
x
t
[
j
]
=
m
a
x
{
k
∣
t
[
0
,
k
−
1
]
=
t
[
j
−
k
,
j
−
1
]
,
k
<
j
}
next[j]=max\{k|t[0,k-1]=t[j-k,j-1],k<j\}
next[j]=max{k∣t[0,k−1]=t[j−k,j−1],k<j}，规定next[0]=-1
2.示例
模式串"ababdac"的next数组为{-1,0,0,1,2,0,1}
3.改进
先用之前的方法得到next[j]的值，假设为k，如果t[j]!=t[k]，则next[j]=k,如果t[j]=t[k]，则next[j]=next[k]，最终计算公式为
{
−
1
,
j
=
0
k
,
t
[
j
]
≠
t
[
k
]
,
其
中
k
=
m
a
x
{
k
∣
t
[
0
,
k
−
1
]
=
t
[
j
−
k
,
j
−
1
]
,
k
<
j
}
n
e
x
t
[
k
]
,
t
[
j
]
=
t
[
k
]
{−1,j=0k,t[j]≠t[k],其中k=max{k|t[0,k−1]=t[j−k,j−1],k<j}next[k],t[j]=t[k]⎩⎪⎨⎪⎧−1,k,next[k],j=0t[j]=t[k],其中k=max{k∣t[0,k−1]=t[j−k,j−1],k<j}t[j]=t[k]
算法
1.算法1-2
功能
给定主串s和模式串t，并给定模式串的next数组，进行模式匹配
算法步骤
(1)定义两个数组i,j，分别表示主串的下标和模式串的下标，初始值都为0
(2)当j=-1或s[i]=t[j]时，i和j同步向后移动
(3)当s[i]!=t[j]时，j=next[j]，回到第(2)步
2.示例\
//求KMP算法中模式串t的next数组
void kmp_next(string t, int* next) {
int i = 0, j = -1;
next[0] = -1;
while (i < t.size()) {
if (j == -1 || t[i] == t[j]) {
++i, ++j;//i和j同步向后移动
if (t[i] == t[j])next[i] = next[j];//改进的next
else next[i] = j;
}
else
j = next[j];
}
}
//KMP模式匹配算法，判断s中是否包含t，如果包含返回t在s中第一次出现的位置，否则返回-1
int kmp(string s, string t) {
int i = 0, j = 0;
int next[t.size()];
kmp_next(t, next);//求t的next数组
while (1) {
if (j == -1 || s[i] == t[j]) {
++i, ++j;//i,j同步后移
if (j == t.size())return i - j;//j到达模式串的最后一个字符的下一个位置，匹配成功
}
else
j = next[j];//j向前移动到下一个位置
}
return -1;//匹配失败
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29