C++實現字符串匹配的KMP算法

講的淺顯易懂，便按照他的思路用C++實現了一篇，代碼如下：

[cpp]
include <iostream>  
#include <string>  
using namespace std; 
 
//計算單次的部分匹配值，如str=="ABCDAB"時返回2  
int single_match(string str) 
{ 
    int n=str.length(); 
    string *prefix=new string[n-1](); 
    string *suffix=new string[n-1](); 
    for(int i=0;i!=n-1;++i){ 
        for(int j=0;j<=i;++j) 
            prefix[i]+=str[j]; 
        for(int k=i+1;k!=n;++k) 
            suffix[i]+=str[k]; 
    } 
 
    int match_num=0; 
    for(int i=0;i<n-1;++i) 
        for(int j=0;j<n-1;++j) 
            if(prefix[i]==suffix[j]) 
                match_num+=prefix[i].length(); 
    return match_num; 
} 
 
//對整個字符串，計算其部分匹配表  
void partial_match_table(string str,int* table) 
{ 
    int n=str.length(); 
    for(int i=0;i!=n;++i){ 
        string sub_str; 
        for(int j=0;j<=i;++j) 
            sub_str+=str[j]; 
        int temp=single_match(sub_str);      
        table[i]=temp; 
    } 
} 
 
// KMP算法  
int Knuth_Morris_Pratt(string str1,string str2,int *table) 
{ 
    int n1=str1.length(); 
    int n2=str2.length(); 
    int i=0; 
    while(i<n1-n2){ 
        int j=0; 
        while(j<n2){ 
            if(str1[i+j]==str2[j]) 
                ++j; 
            else 
                break; 
        } 
        if(j==n2) 
            break; 
        else if(j==0) 
            ++i; 
        else 
            i+=j-table[j-1]; 
    } 
 
    if(i>n1-n2) 
        return -1; 
    return i; 
} 
 
int main() 
{ 
    string str1("BBC ABCDAB ABCDABCDABDE"); 
    string str2("ABCDABD"); 
    int n=str2.length(); 
    int *table=new int[n]; 
 
    for(int i=0;i<n;++i) 
        cout<<table[i]<<' '; 
    cout<<endl; 
     
    cout<<Knuth_Morris_Pratt(str1,str2,table)<<endl; 
    return 0; 
} 

#include <iostream>
#include <string>
using namespace std;

//計算單次的部分匹配值，如str=="ABCDAB"時返回2
int single_match(string str)
{
 int n=str.length();
 string *prefix=new string[n-1]();
 string *suffix=new string[n-1]();
 for(int i=0;i!=n-1;++i){
  for(int j=0;j<=i;++j)
   prefix[i]+=str[j];
  for(int k=i+1;k!=n;++k)
   suffix[i]+=str[k];
 }

 int match_num=0;
 for(int i=0;i<n-1;++i)
  for(int j=0;j<n-1;++j)
   if(prefix[i]==suffix[j])
    match_num+=prefix[i].length();
 return match_num;
}

//對整個字符串，計算其部分匹配表
void partial_match_table(string str,int* table)
{
 int n=str.length();
 for(int i=0;i!=n;++i){
  string sub_str;
  for(int j=0;j<=i;++j)
   sub_str+=str[j];
  int temp=single_match(sub_str);  
  table[i]=temp;
 }
}

// KMP算法
int Knuth_Morris_Pratt(string str1,string str2,int *table)
{
 int n1=str1.length();
 int n2=str2.length();
 int i=0;
 while(i<n1-n2){
  int j=0;
  while(j<n2){
   if(str1[i+j]==str2[j])
    ++j;
   else
    break;
  }
  if(j==n2)
   break;
  else if(j==0)
   ++i;
  else
      i+=j-table[j-1];
 }

 if(i>n1-n2)
  return -1;
 return i;
}

int main()
{
 string str1("BBC ABCDAB ABCDABCDABDE");
 string str2("ABCDABD");
 int n=str2.length();
 int *table=new int[n];

 for(int i=0;i<n;++i)
  cout<<table[i]<<' ';
 cout<<endl;
 
 cout<<Knuth_Morris_Pratt(str1,str2,table)<<endl;
 return 0;
}
代碼的缺點是對字符串的處理太過生硬。習慣了python對string類型的切片操作後，對C++中string類型的使用太生疏，以至於取出子串的操作都用遍歷相加來實現……

歡迎大家提出修改意見哈~