串匹配算法
问题：给定二个字符串S和T,在主串S中查找子串T的过程称之为字符串匹配问题（string matching,也称之为模式匹配)。在文本处理系统，操作系统，编译系统，数据库系统以及internet信息检索中，串匹配是使用最频繁操作。
有蛮力法，即BF(暴力匹配算法，和KMP算法。
我只会bf算法，kmp还是有问题。
思路
从主串S开始的一个字符串和子串T的第一个字符串进行比较，若相等，则比较二者的后续字符；若不相等，则主串S的第二个字符和子串T的第一个字符进行比较，重复上述过程，若T中的字符全部匹配完，则说明本次匹配成功，若S中字符全部比较完毕，则匹配失败。
#include<iostream>
#include<time.h>
using namespace std;
int bfstring(char k[],char s[]);
int main()
{
char k[]="abcabcacb";
char s[]="abcac";
clock_t start,finish;
int index;
double duration;
start= clock();
for(int z=0; z<1000000; z++) //扩大匹配时间
{
index=bfstring(k,s);
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
if(index==0)
cout<<"匹配失败"<<endl;
else
cout<<"本次匹配的开始位置:"<<index<<endl;
return 0;
}
//k为主串，S为字串。
int bfstring(char k[],char s[])
{
int i=0,j=0;
int index=0;
while(k[i]!='\0'&&s[j]!='\0')
{
if(k[i]==s[j])
{
i++;
j++;
}
else{
index++;
j=0;
i=index;
}
}
if(s[j]=='\0')
return index+1; //返回本次匹配的开始位置。
return 0;
}结果
time=0.074000 seconds
本次匹配的开始位置:4
Press any key to continuekmp算法。
主要是寻找next的值。
#include<iostream>
#include<time.h>
using namespace std;
int kmp(char k[],char s[]);
void getNext(char s[],int next[]);
int main()
{
char k[]="abcabcacb";
char s[]="abcac";
clock_t start,finish;
int index;
double duration;
start= clock();
for(int z=0; z<1000000; z++) //扩大匹配时间
{
index=kmp(k,s);
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
if(index==0)
cout<<"匹配失败"<<endl;
else
cout<<"本次匹配的开始位置:"<<index<<endl;
return 0;
}
//k为主串，S为字串。
int kmp(char k[],char s[])
{
int i=0,j=0;
int next[100];
getNext(s,next);
while(k[i]!='\0'&&s[j]!='\0')
{
if(k[i]==s[j])
{
i++;
j++;
}
else{
j=next[j];
if(j==-1)
{
i++;
j++;
}
}
}
if(s[j]=='\0')
return i-strlen(s)+1; //返回本次匹配的开始位置。
return 0;
}
void getNext(char s[],int next[])
{
int i,j,len;
next[0]=-1;
for(j=1; s[j]!='\0'; j++) //依次求next[j]
{
// 相等的子串最大长度为j-1
for(len=j-1; len>=1; len--)
{
//依次比较 S[0]~S[len-1]与S[j-len]~s[j-1]
for(i=0; i<len; i++)
if(s[i]!=s[j-len+i])
break;
if(i==len)
{
next[j]=len;
break;
}
}
if(len<1) //其它情况无相等字符串
next[j]=0;
}
}结果
time=0.135000 seconds
本次匹配的开始位置:4
Press any key to continue本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读