串的模式匹配就是从一个主串中找到子串出现的位置,如主串是"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;
}
|
下面是两个测试用例:
![](http://pic002.cnblogs.com/images/2011/103496/2011042220245820.png)
![](http://pic002.cnblogs.com/images/2011/103496/2011042220251450.png)
STL总是出奇地快,Sunday并不是总比最笨的BF算法快.