字符串匹配算法之KMP算法

這個算法是字符串匹配算法中的佼佼者，僅利用O(lengthText + lengthPattern)的時間就完成了匹配任務。他快速的原因是無須回溯。這個算法最高深的也是最難懂的地方在於，兩個串進行匹配，成功與否竟然只和模板串有關系，和目標串是沒有關系的。當模板串在j位置匹配失敗後，不用重新到0位置，下一次的位置應該再next[j]的位置。 下面是生成next數組的函數： [cpp]   void GetNext(string Pattern, vector<int> &next)   {       int j = 0;       int k = -1;       int lenP = Pattern.length();       next.assign(8, -1);          while (j < lenP)       {           if ((k == -1) || (Pattern[j] == Pattern[k]))           {               j++; k++;               next[j] = k;           }            else           {               k = next[k];           }       }   }   下面是KMP算法： [cpp]   int KMP(string Text, string Pattern, vector<int> &next, int TdefPos = 0)   {       int posP = 0, posT = TdefPos;       int lenP = Pattern.length();       int lenT = Text.length();          while ((posP < lenP) && (posT < lenT))       {           if ((posP == -1) || Pattern[posP] == Text[posT])           {               posP++; posT++;           }            else           {               posP = next[posP];           }       }          if (posP < lenP)       {           return -1;       }        else       {           return (lenT - lenP);       }   }