大家好,又见面了,我是你们的朋友全栈君。
现实生活中,字符串匹配在很多的应用场景里都有着极其重要的作用,包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等等,至此诞生了很多的算法,那么我们今天就来探索这两种经典的算法。
首先我们需要了解到什么是kmp算法和strstr函数 概念如下:KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。(来自百度百科) strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是,则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串;否则,返回NULL。(来自百度百科)
在这里我们很明显的看到,strstr作为最原始的算法,他的最差时间复杂度为O(len(s)*len(t)),效率是非常的低下的,而经过改良优化后的kmp算法则为O(m+n),两者进行一对比发现差距真的很大,而且kmp算法算然把字符串遍历了一遍,但如果不遍历一遍,怎么可能匹配的出来呢?
对比发现,strstr函数对整个母串和字串都进行了多次的遍历,做了很多的重复工作,浪费了一些我们已经知道的信息,直接导致了时间的消耗,大大的降低了效率。例如,一个长度为9的t字符串abcdabcad,字串s为abca,当我们的指针走到t[4]的时候,发现匹配失败,此时s位置的指针已经走到了s[3]的位置,又得重新回到s[0],继续和t[4],进行匹配,重复此步骤,直到遍历完字符串t为止。这样子的话,重复匹配了s的字符n多次,所以效率极低。
strstr代码如下:
size_t Find(const char* str, size_t pos = 0) const
//(两个指针,字串和父串从第一个开始字符匹配,如果第一个字符匹配后,
//开始逐个字符串匹配到最后一个,中途若有不同,字串退回开始,父串不变,继续重复操作,直至找到为止)
{
if (pos > _size)
{
cout << "pos位置有误报<<endl";
}
size_t index_str = 0;
//若循环条件退出,要么找到了,要么找到结尾也没找到
while (_str[index_str] != '\0')
{
if (_str[index_str] == *str)//从开头开始匹配字符
{
size_t Find_index = index_str;
size_t str_index = 0;
while (1)
{
//如果遍历完了str没有停下来,就表示找到了
if (str[str_index] == '\0')
{
return index_str;
}
//如果不相等就结束循环
if (_str[Find_index] != str[str_index])
{
break;
}
Find_index++;
str_index++;
}
//跳出循环
}
//不匹配继续向前找
index_str++;
}
return -1;
}
可能有人会想,为啥我们敢跳过那段长度为next的距离呢,再来一个图解。
竖线叫abc吧。
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
using namespace std;
typedef char* String;
//得到next数组
void Get_Next(String T, int *next)
{
int j, k;
j = 0;
k = -1;
next[0] = -1;
while (j < strlen(T))
{
if (k == -1 || T[j] == T[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
//KMP算法
int KMP(String S, String T, int *next)
{
int i = 0, j = 0;
Get_Next(T, next);
int slen = strlen(S);
int tlen = strlen(T);
while (i < slen && j < tlen)
{
if (j == -1 || S[i] == T[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == tlen)
{
return i - tlen;
}
else
{
return -1;
}
}
void main()
{
cout << "next就是输入的那一串字符每一个字符多对应的下标 " << endl;
int N;
cout << "请输入你想测试的次数:" << endl;
cin >> N;
while (N--)
{
cout << endl;
cout << "请输入一串字符:" << endl;
char S[255];
char T[255];
cin >> S >> T;
int next[255];
int i = 1;
//cout << strlen(S) << endl;
Get_Next(T, next);
cout << "模式每一个字符对应的next的值为:" << endl;
for (i = 0; i < strlen(T); i++)
{
printf("%d ", next[i]);
}
cout << endl;
cout << "匹配出现的位置:" << KMP(S, T, next) << endl;
}
cout << endl;
system("pause");
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/153013.html原文链接:https://javaforall.cn