串的模式匹配就是从一个主串中找到子串出现的位置,如主串是"asd234",子串是"d2",那么算法返回的结果就应该是2.
一种最朴素的想法就是BF算法,我就不讲了," 最朴素"嘛,就是你脑子里现在想的那种算法.
比较优一点的是KMP算法.
更优的是BM算法.
BM的改进算法是Sunday Algorithm.
现在我给出BF和Sunday两种算法的代码,然后再和STL中string在find函数进行比较.
STL中string在find函数示例:
string name("AnnaBelle");
string::size_type pos=name.find("Anna"); //pos==0
#include<iostream>
#include<cstring>
#include<ctime>
using namespace std;
int BF(const string &str1,const string &str2){
int len1=str1.size();
int len2=str2.size();
int i=0;
int j=0;
while(i<len1 && j<len2){
if(str1[i]==str2[j]){
i++;
j++;
}
else{
i+=1-j;
j=0;
}
}
if(j==len2)
return i-j;
else
return -1;
}
int findChar(const string &str,char c){
int len=str.size();
for(int i=len-1;i>=0;i--){
if(str[i]==c){
return i;
}
}
return -1;
}
int Sunday(const string &str1,const string &str2){
int len1=str1.size();
int len2=str2.size();
int i=0;
int j=0;
int begin=i;
while(i<len1 && j<len2){
if(str1[i]==str2[j]){
i++;
j++;
}
else{
int index=findChar(str2,str1[begin+len2]);
if(index<0){
begin+=len2+1;
j=0;
i=begin;
}
else{
int ps=len2-index;
begin+=ps;
j=0;
i=begin;
}
}
}
if(j==len2)
return i-j;
else
return -1;
}
int main(){
const int N=1000000;
string str1,str2;
cout<<"Input MainString: ";
getline(cin,str1);
cout<<"Input SubString: ";
getline(cin,str2);
clock_t start,finish;
start=clock();
for(int i=0;i<N;i++)
BF(str1,str2);
finish=clock();
cout<<"BF:"<<BF(str1,str2)<<"\t"<<(double)(finish-start)/CLOCKS_PER_SEC<<"s"<<endl;
start=clock();
for(int i=0;i<N;i++)
Sunday(str1,str2);
finish=clock();
cout<<"Sunday:"<<Sunday(str1,str2)<<"\t"<<(double)(finish-start)/CLOCKS_PER_SEC<<"s"<<endl;
start=clock();
for(int i=0;i<N;i++)
str1.find(str2);
finish=clock();
cout<<"STL:"<<str1.find(str2)<<"\t"<<(double)(finish-start)/CLOCKS_PER_SEC<<"s"<<endl;
return 0;
}
|
下面是两个测试用例:
STL总是出奇地快,Sunday并不是总比最笨的BF算法快.