C++实现：BF算法和KMP算法

BF算法：

int BF_Find(string& s,string& t)
{
int i=0,j=0,count=0;
while(i<s.size())
{

if(s.at(i)==t.at(j))
{
i++;
j++;
count++;}
   else
   {
   i++;
   j=0;
   count=0;
}
if(count==t.size())
{
cout<<"模式匹配成功,起始位置是:"<<i-count+1<<endl;
return (i-count+1);
}

}
    cout<<"字符串匹配失败!"<<endl;
return 0;
}

改进后的BF算法效率更高即KMP算法:

void GetNext(string& s,int *next)
{
int len = s.size();
     next[0] = 0;
     next[1] = 0;
     int i = 1;
     while(i < len - 1)
    {
            int j = next[i];

while(j > 0 && s.at(j) != s.at(i)) j = next[j];

if(s.at(j) == s.at(i))  next[i + 1] = j + 1;
            else next[i + 1] = j;

            i++;
      }



}
int KMP_Find(string& s,string&t)
{
 int i=0,j=0;
 int n =t.size();
 int *next = new int[n];
 GetNext(t,next);
 while(i<s.size()&&j<t.size())
  {
     if((j == 0)||(s.at(i)==t.at(j)))
              {
      i++;
                  j++;
              }
              else
              {
                  j = next[j];
              }
   }
  if(j==t.size())
  {
   int index=i-t.size()+1;
   cout<<"子串从长串的第"<<index<<"位开始匹配成功!"<<endl;  
   return index;
  }
     cout<<"字符串匹配失败!"<<endl;
  return 0;
}
测试代码：

#include "stdafx.h"#include <iostream>#include <string>using namespace std; int _tmain(int argc, _TCHAR* argv[]){string str1,str2;cout<<"请输入主串:"<<endl;cin>>str1;cout<<"请输入子串:"<<endl;cin>>str2;KMP_Find(str1,str2);return 0;}