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;
}