数据结构学习之字符串匹配算法(BF||KMP)
0x1 实验目的
通过实验深入了解字符串常用的匹配算法(BF暴力匹配、KMP、优化KMP算法)思想。
0x2 实验要求
编写出BF暴力匹配、KMP、优化KMP的代码模型
0x2 代码
0x2.1.1 BF暴力匹配
#include <iostream>
#include <string>
using namespace std;
int BF1(string s1,string s2)
{
int len=s2.length();
for(int i=0;i<s1.length();i++)
{
int n=len;
int j=i;
while(n)
{
//cout<< s1[j] <<endl;
if(s1[j++] != s2[len-n])
break;
n--;
}
if(n==0)
return i+1;
}
return -1;
}
int BF2(string s1,string s2)
{
int i=0;
int j=0;
while(i<s1.length() && j<s2.length())
{
if(s1[i]==s2[j])
{
i++;
j++;
}else
{
i=i-j+1;
j=0;
}
}
if(j>=s2.length())
return (i-j+1);
else
return -1;
}
int main()
{
string s1="asfasgasgsd";
string s2="asg";
cout<< BF1(s1,s2) <<endl;
cout<< BF2(s1,s2) <<endl;
return 0;
}
0x2.1.2 结果
0x2.1.3 体会
我写了两种,一开始我没看书自己意淫了第一种出来,代码不够书本简洁,本着向优秀代码学习的精神,还有对应对应下面KMP的匹配过程,第二种写法更有益于学习。过程主要是,while(i<s.length() && j<t.length())来判断退出,其中跟kmp不同的是,i需要i-j+1,j=0回溯,该算法的时间复杂度0(n*m)。
0x2.2 KMP || KMP优化
#include <iostream>
#include <string>
#define maxsize 200+7
using namespace std;
int next[maxsize];
int nextval[maxsize];
void GetNext(string s,int next[])
{
int j=0,k=-1;
next[0]=-1;
while(j<s.length()-1) //因为数组下标最大是s1.length()-1,下面是j++故j可以到达最大值
{
if(k==-1 || s[j]==s[k])
{
j++,k++;
next[j]=k;
}else
{
k=next[k];
}
}
}
void GetNextVal(string s,int nextval[])
{
int j=0,k=-1;
nextval[0]=-1;
while(j<s.length()-1)
{
if(k==-1 || s[j]==s[k])
{
j++,k++;
if(s[j]!=s[k])
nextval[j]=k;
else
nextval[j]=nextval[k];
}else
{
k=nextval[k];
}
}
}
//KMP优化
int KMPIndex1(string s,string t)
{
int i=0,j=0;
int next[maxsize];
GetNext(t,next);
while(i<s.length() && j<t.length())
{
if(j==-1 || s[i]==t[j])
{
i++,j++;
}else
{
j=next[j];
}
}
if(j>=t.length())
return(i-t.length());
else
return -1;
}
//KMP优化
int KMPIndex2(string s,string t)
{
int i=0,j=0;
int nextval[maxsize];
GetNextVal(t,nextval);
while(i<s.length() && j<t.length())
{
if(j==-1 || s[i]==t[j])
{
i++,j++;
}else
{
j=nextval[j];
}
}
if(j>=t.length())
return(i-t.length());
else
return -1;
}
int main()
{
string s="aaaaab";
string t="aaab";
cout<< KMPIndex1(s,t) <<endl;
cout<< KMPIndex2(s,t) <<endl;
return 0;
}
0x2.2.1 结果
0x2.2.2 体会
kmp算法主要思想是利用模式串自身的特点,避免主串的回溯过程,同时通过next数组,也减少了模式串的回溯长度。
首先是定义:
\[next[j]=\left\{\begin{matrix}-1 \qquad 当j=0时
\\MAX \left \{ k|0<k<j\ 且 \ t_{0}t_{1}\cdots t_{k-1} = t_{j-k}t_{j-k+1}\cdots t_{j-1}\right \} \ 当此集合非空时
\\ 0 \qquad 其他情况
\end{matrix}\right.
\]
\\MAX \left \{ k|0<k<j\ 且 \ t_{0}t_{1}\cdots t_{k-1} = t_{j-k}t_{j-k+1}\cdots t_{j-1}\right \} \ 当此集合非空时
\\ 0 \qquad 其他情况
\end{matrix}\right.
\]
主要思想是:
比如一个模式串 ababb 显然前4个字符串满足 ab=ab 也就是$$t_{0}t_{1}=t_{2}t_{3}$$ 当你去用模式串去匹配串ababaababb的时候可以发现$$t_{4} \neq s_{4}$$,这个时候就直接可以跳转到 $$s_{2}$$ 开始 而不是从$$s_{1}$$开始,关于这个证明其实也很简单,如下:
aba $$\neq$$ bab 然后你发现这里了没有,从$$s_{1}$$开始其实就是从bab开始很明显就是不等,其实kmp就是这种规律,找出最大长度的前后缀,那么就确定了这个模式串滑动的长度,说的更简单点就是模式串包含了主串的信息,模式串跟主串的比较就可以转换为模式串跟自己的比较,就像上面的例子,通过反证法可以得到移动<next[j]的话必定会不想等。
代码重点是:
//初始化
next[0]=-1;
int j=0,k=-1;
while(j<s.length()-1)
{
if(k==-1 || s[j]==s[k])
{
j++,k++;
next[j]=k; //重点
}else
{
k=next[k]; //重点 abdbabc 显然c -> ab开头的两个字符,d不等于c,那么只能从a=c这里去比较了next[2]=0
}
}
0x3 最近学习总结
最近感觉自己特别浪,要学的东西还有很多,平时效率也好低,数据结构的作业也拖了好久,以前都是4天一次,这次竟然拖了那么10多天,最近要抓紧空闲时间去补回来了,下篇写一些递归的题目,介绍一些好玩的知识点。