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新闻热点
疑难解答
