2.串的模式匹配
-
什么是字符串的模式匹配?
在主串中找到与模式串相同的子串,并返回其所在位置。
- 模式串:要匹配的一串。注:子串是主串的一部分,一定在主串中存在,但模式串不一定在主串中找得到。
2.1 朴素模式匹配算法
-
思路
暴力求解,一个字符一个字符对比下去。
-
代码思路
1.给主串一个指针 i,模式串指针 j,两个指针都指向第一个字符;
2.若 i 和 j 所指字符相等,i+1,j+1;
3.若 i 和 j 所指字符不相同,j 回到模式串第一个字符,i 指向下一个子串起始位置;
4.若 j 超过模式串的长度,则匹配成功。
int Index(SString S,SString T){
int i=1,j=1; //分别扫描主串和模式串
while(i<S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){
i++;j++; //继续比较后继字符
}
else{
i=i-j+2; //到下一个子串的起始位置
j=1;
}
}
if(j>T.length)
return i-T.length;
else
return 0;
}
-
时间复杂度
最坏情况:每个子串都要对比m个字符,共n-m+1个子串,复杂度= O ( ( n − m + 1 ) m ) = O ( n m ) O((n-m+1)m)=O(nm) O((n−m+1)m)=O(nm)
2.2 KMP算法
-
核心思想
从模式串本身的结构着手,若已匹配相等的前缀序列中有某个后缀正好是模式串的前缀,则可将模式串向后滑动到与这些相等字符对齐的位置。
-
设置next数组,
next[a]=b
意思为: 当模式串中第a个元素匹配失败时,令主串指针i不变,模式串指针j=b。
即当第a个元素匹配失败时,模式串回溯到第b个元素继续与主串匹配。
-
KMP算法=模式匹配过程+next数组求解
-
-
时间复杂度
O ( m + n ) O(m+n) O(m+n)
其中,求next数组时间复杂度 O ( m ) O(m) O(m)
模式匹配过程最坏时间复杂度 O ( n ) O(n) O(n)
2.2.1 模式匹配
-
模式匹配过程(还未求next数组)
1.分别设置i和j指针,指向主串和模式串;
2.如果i和j指针指向的字符相同,i和j都加1;
3.如果不相同,j回溯到模式串的上一个字符,即
j=next[j]
。4.如果j等于0(模式串第一个元素下标为1),则i和j都加1。
int Index_KMP(SString S,SString T,int next[]){ int i=1,j=1; while(i<=S.length&&j<=T.length){ if(j==0||S.ch[i]==T.ch[j]){ i++; j++; } else{ j=next[j]; } } if(j>T.length) return i-T.length; else return 0; }
2.2.2 求next数组
-
next数组作用
当模式串的第j个字符失配时,从模式串的第next[j]个继续往后匹配。
-
next数组手算方法
1.对于任何模式串:next[1]=0,next[2]=1
2.对其他的next:在不匹配的位置前,划一条分界线,模式串一步步往后退,直到分界线前能对上,或模式串完全跨过分界线为止。此时j指哪,next数组值就是多少。
- 即
next[i]
存储的是 T[1:i] 这个子串的最长公共前后缀的长度。
- 即
-
next数组的优化
next
数组优化为nextval
在原
next
数组基础上,若j对应的模式串元素和next[j]
对应的模式串元素相等,则令nextval[j]=nextval[next[j]]
nextval[1]=0; for(int j=2;j<=T.length;j++){ if(T.ch[next[j]]==T.ch[j]) nextval[j]=nextval[next[j]]; else nextval[j]=next[j]; }
*完整代码 KMP
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MaxSize 99
typedef struct {
char ch[MaxSize];
int length;
}SString;
void StrAssign(SString& T, char chars[]) {
for (int i = 0; i <= strlen(chars); i++)
T.ch[i+1] = chars[i];
T.length = strlen(chars);
}
void PrintS(SString S) {
printf("Str:");
for (int i = 1; i <= S.length; i++)
printf("%c", S.ch[i]);
printf("\n");
}
//KMP模式匹配算法
//S:主串
//T:模式串
int Index_KMP(SString S, SString T, int next[]) {
int i = 1; //主串S的指针
int j = 1; //模式串T的指针,数组下标都从1开始
while (i <= S.length && j <= T.length) {
if (j == 0 || S.ch[i] == T.ch[j]) { //模式串已到头或当前字符相同
i++; j++; //继续比较后继字符
}
else {
j = next[j]; //模式串向右移动
}
}
if (j > T.length)
return i - T.length; //匹配成功
else
return 0;
}
//求next数组
void get_next(SString T, int next[]) {
int i = 1, j = 0;
next[1] = 0;
while (i < T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) { //当前字符与前缀字符相同
i++; j++;
next[i] = j; //当前位置的next值为前缀字符个数
}
else {
j = next[j]; //不相同则回溯
}
}
}
//next数组优化
void get_nextval(SString T, int nextval[]) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < T.length) {
if (j == 0 || T.ch[i] == T.ch[j]) { //当前字符与前缀字符相同
i++; j++;
if (T.ch[i] != T.ch[j])
nextval[i] = j; //当前位置的nextval值为前缀字符个数
else
nextval[i] = nextval[j]; //如果当前字符与前缀字符相同,则继续向前递归
}
else {
j = nextval[j]; //不相同则回溯
}
}
}
int main() {
SString S, T;
char s[] = "abcabcde";
char t[] = "abcd";
StrAssign(S, s);
StrAssign(T, t);
PrintS(S);
PrintS(T);
int next[MaxSize];
get_next(T, next);
int nextval[MaxSize];
get_nextval(T, nextval);
int pos = Index_KMP(S, T, next);
if (pos != 0) {
printf("Pattern found at position: %d\n", pos);
}
else {
printf("Pattern not found.\n");
}
pos = Index_KMP(S, T, nextval);
if (pos != 0) {
printf("Pattern found at position: %d\n", pos);
}
else {
printf("Pattern not found.\n");
}
return 0;
}