一 字符串匹配算法—BF算法

BF算法简称暴力破解算法，时间复杂度很容易计算为O（m*n）(当n>>m时候)
本身字符串S，长度为m
模式字符串T,长度为n
最差情况，需要匹配(n-m)m+m才可以成功，所以时间复杂度就是O((n-m)m+m)=O(nm+m-mm)

• BF算法

//BF算法
int Index_BF(string s,string t)
{int i=0,j=0;while(i<s.length()&&j<t.length()){if(s[i]==t[j]) {++i;++j;}else {i=i-j+1;j=0;}}if(j>=t.length()) return i-t.length();//如果匹配成功了，就返回首个匹配成功的字符else return 0;//否则返回0}

• 改进BF算法

int Index_Imporvent_BF(string s,string t,int pos=0)
{int i=pos,j=0;while(i<s.length()&&j<t.length()){if(s[i]==t[j]) {++i;++j;}else {i=i-j+1;j=0;}}if(j>=t.length()) return i-t.length();//如果匹配成功了，就返回首个匹配成功的字符else return 0;//否则返回0}

• 全部代码

#include <iostream>
#include "string"
using namespace std;
//BF算法
int Index_BF(string s,string t)
{int i=0,j=0;while(i<s.length()&&j<t.length())//i没有了就是没有匹配到字符串，j没有了就是匹配到，只要其中一个不满足就退出循环{if(s[i]==t[j]) {++i;++j;}else {i=i-j+1;j=0;}}if(j>=t.length()) return i-t.length();//如果匹配成功了，就返回首个匹配成功的字符else return 0;//否则返回0}
int Index_Imporvent_BF(string s,string t,int pos=0)
{int i=pos,j=0;while(i<s.length()&&j<t.length())//i没有了就是没有匹配到字符串，j没有了就是匹配到，只要其中一个不满足就退出循环{if(s[i]==t[j]) {++i;++j;}else {i=i-j+1;j=0;}}if(j>=t.length()) return i-t.length();//如果匹配成功了，就返回首个匹配成功的字符else return 0;//否则返回0}int main() {std::cout << "Hello World!\n";std::cout<<"reslut of BF   "<<Index_BF("aaasdfg", "sdf")<<endl;std::cout<<"reslut of Improvement_BF   "<<Index_Imporvent_BF("aaasdfg", "aa",3)<<endl;
}

• 输出结果