1 简单的模式匹配算法
思想: 将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串或所有子串都不匹配为止。
具体代码展示:
1)串的初始化工作
#include<stdio.h>
#define MAXLEN 255 //预定义最大串长
typedef struct {
char ch[MAXLEN];//每一个分量存储一个字符
int length;//串的实际长度
}SString;
// 字符串下标从1开始记录,将ch[0]设置为‘\0’
SString createString() {
SString str;
str.ch[0] = '\0';
str.length = 0;
return str;
}
//赋值操作
void StrAssign(SString& S, char chars[])//生成串S
{
int i = 0;
while (chars[i] != '\0')
{
//第一个位置不用
S.ch[i+1] = chars[i];//将字符串常量的值赋值给S
i++;
}
S.length = i+1;
}
//打印串
void PrintString(SString S) {
if (S.length == 0) {
printf_s("当前串为空");
}
else {
for (int i = 1; i < S.length; i++) {
printf_s("%c", S.ch[i]);
}
printf_s("\n");
}
}
2)简单模式匹配算法实现
int Index(SString S, SString T) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {
//相等则指针+1
if (S.ch[i] == T.ch[j]) {
i++;
j++;
}
else {
i = i - j + 2;//主串指针退回到当前指针的下一个位置
j = 1;//模式串指针退回到第一个位置
}
//放在这里判断是为了返回第一个匹配的子串位置,
//T的长度是实际长度+废弃的第一个位置长度,所以这里减一
//说明匹配完成,指向T的最后一个元素的下一个位置
if (j > T.length - 1) {
return i - T.length + 1;
}
}
return 0;
}
3)主函数调用
int main(){
SString S=createString(), T=createString();
char ch1[] = { "aaabaabcaabdabacaabc" };
char ch2[] = { "aabc" };
StrAssign(S, ch1);
StrAssign(T, ch2);
printf_s("S串元素为:");
PrintString(S);
printf_s("T串元素为:");
PrintString(T);
printf_s("----------------------------\n");
printf_s("简单模式匹配算法:\n");
printf_s("子串在主串位置为:%d", Index(S, T));
}
4)结果展示
注意:子串匹配的是在主串中首次出现的,在所给例子中,子串出现了两次,但是记录的位置是第一次出现的位置。
2 KMP算法
简单模式匹配算法: 当子串的某一字符与主串对应的字符不匹配时,主串的指针会回溯到扫描第一个位置的下一个位置,子串的指针也会回溯到第一个位置,然后重新匹配。但是没必要去比较后面的某些位置,因为在主串中,匹配失败的那个字符肯定不是b,所以下一次指针位置应该为3,而不是2,如下图所示。
所以,也就引出了KMP算法,即将子串的指针位置组成一个next数组,这样就极大地减少比较的次数。next[i]的含义是在第i个字符与主串发生失配时,则跳到字串的next[i]位置重新与主串当前位置进行比较。
比如主串为:abacaabefc,子串为aab,则next数组为0,1,2。手算可以推出来的,并且要注意的是next[1]肯定等于0,为什么?因为当子串的第一个字符匹配失败时,那肯定转到第二个位置继续匹配。
具体代码展示:
1)next数组代码求解过程如下(不作过多讲解)
//求next数组
//next[1]为0,next[2]为1
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;
}
else {
j = next[j];
}
}
}
2)KMP算法实现
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-1) {
return i - T.length+1;
}
}
return 0;
}
3)主函数调用
int main(){
SString S=createString(), T=createString();
char ch1[] = { "abacaabefc" };
char ch2[] = { "aab" };
StrAssign(S, ch1);
StrAssign(T, ch2);
printf_s("S串元素为:");
PrintString(S);
printf_s("T串元素为:");
PrintString(T);
printf_s("----------------------------\n");
printf_s("简单模式匹配算法:\n");
printf_s("子串在主串位置为:%d", Index(S, T));
printf_s("\n----------------------------\n");
printf_s("KMP算法:\n");
int next[10] = { -1 };//第一个值弃用
get_next(T, next);
printf_s("next数组元素为:");
for (int i = 1; i < T.length;i++) {
printf_s("%d ", next[i]);
}
printf_s("\n子串在主串位置为:%d", Index_KMP(S, T,next));
}
4)运行结果
3 KMP算法改进
KMP算法问题: 当子串’aaaab’与’aaabaaaab’匹配时,当i=4,j=4时,子串与主串匹配失败,用之前的next数组还需要和S4和P3、S4和P2、S4和P1比较,显然没有意义。问题就出在Pj=Pnext[j]上,因为当Pj≠Sj时,下次匹配的必然是Pnext[j]和Sj比较,如果Pj=Pnext[j],相当于重复匹配相同字符,那怎么办,可以继续递归,将next[j]修改为next[next[j]]直至两者不相等为止。
具体代码实现:
1)next数组优化
//求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;
}
else {
nextval[i] = nextval[j];
}
}
else {
j = nextval[j];
}
}
}
2)主函数调用文章来源:https://www.toymoban.com/news/detail-415626.html
int main(){
SString S=createString(), T=createString();
char ch1[] = { "aaabaaaab" };
char ch2[] = { "aaaab" };
StrAssign(S, ch1);
StrAssign(T, ch2);
printf_s("S串元素为:");
PrintString(S);
printf_s("T串元素为:");
PrintString(T);
printf_s("----------------------------\n");
printf_s("简单模式匹配算法:\n");
printf_s("子串在主串位置为:%d", Index(S, T));
printf_s("\n----------------------------\n");
printf_s("KMP算法:\n");
int next[10] = { -1 };//第一个值弃用
get_next(T, next);
printf_s("next数组元素为:");
for (int i = 1; i < T.length;i++) {
printf_s("%d ", next[i]);
}
printf_s("\n子串在主串位置为:%d", Index_KMP(S, T,next));
printf_s("\n----------------------------\n");
get_nextval(T, next);
printf_s("nextval数组元素为:");
for (int i = 1; i < T.length; i++) {
printf_s("%d ", next[i]);
}
printf_s("\n子串在主串位置为:%d\n", Index_KMP(S, T, next));
return 0;
}
3)运行结果
文章来源地址https://www.toymoban.com/news/detail-415626.html
4 时间复杂度比较
- 简单模式匹配算法: 最坏复杂度为O(mn)
-
KMP算法: 最坏时间复杂度为O(m+n)
其中求next数组时间复杂度为O(m)
模式匹配过程中最坏时间复杂度为O(n)
到了这里,关于串的模式匹配算法(超详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!