KMP雖然經典，但是并不是最快的，KMP在預處理模式串的時候還沒有讓j指針（指向模式串的指針）盡量跳過最大可跳過的距離，可以參考Sunday字符串匹配算法。 KMP算法是通過分析子串，預先計算每個位置發生不匹配的時候，所需GOTO的下一個比較位置，整理出來一個next數組，然后在上面的算法中使用。
[C/C++]代碼//kmp.h : kmp算法。//*************************************************************************//Copyright: //Author: Sail//Filename: kmp//Last Mod time: //*************************************************************************//Remarks://kmp解決了模式串指針回溯的問題，通過對模式串進行預處理（尋找最長前綴），//先將回溯的距離計算好，從而使算法復雜度從樸素的O(mn)降低到O(m+n)////*************************************************************************#ifndef _my_kmp_#define _my_kmp_#include <string.h>#include <vector>using std::vector;//res 用來存放匹配的位移inline void kmp(const char * ori, const char * pat, vector<int> * res){int olen=strlen(ori);int plen=strlen(pat);int * next=new int[plen];next[0]=0;for (int i=1,j=0;i<plen;++i){j=next[i-1];while (j>0&&pat[j]!=pat[i]){j=next[j-1];}if (pat[j]==pat[i]){++j;}next[i]=j;}for (int i=0,j=0;i<olen;++i){while (j>0&&ori[i]!=pat[j]){j=next[j-1];}if (ori[i]==pat[j]){++j;}if (j==plen){(* res).push_back(i-j+1);}}delete []next;}#endif新聞熱點
疑難解答
