字符串匹配算法（BF、KMP）

一字符串匹配算法—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;
}