KMP(字符串匹配)算法

这里不做研究，只是为个人加深印象而写，以便日后查阅，具体可以参考下面两篇文章，写的比较详细：

http://wenku.baidu.com/view/5045c90cba1aa8114431d994.html

http://www.matrix67.com/blog/archives/115

 

C++代码

#include<iostream>//获取模式数组void GetNext(const char* p,int next[]){int m=0;int n=-1;next[0] = -1;while (p[m+1] != '/0'){if (n==-1 || p[m]==p[n]){++m;++n;if (p[m]!=p[n])next[m] = n;elsenext[m]=next[n];}else{n = next[n];}}}//查找匹配位置int KMP(const char* pSchar,const char* pDchar,int pos){int i = pos;int j = 0;int index = 0;int* next = new int[strlen(pDchar)+1];GetNext(pDchar,next);while(pSchar[i] != '/0' && pDchar[j] != '/0'){if (pSchar[i] == pDchar[j]){++i;++j;}else{index += j - next[j];if (next[j] != -1)j = next[j];else{j = 0;++i;}}}delete[] next;if (pDchar[j] == '/0')return index;elsereturn -1;}void main(){char* s = "abababaabab";char* p = "aaba";int index = -1;index = KMP(s,p,0);if (index != -1)printf("从第%d个字符开始匹配",index+1);elseprintf("%s","没有找到匹配");}

 

Delphi代码

unit Unit1;interfaceuses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;type TForm1 = class(TForm) Button1: TButton; procedure Button1Click(Sender: TObject); private { Private declarations } //模式数组 arrNext : array of Integer; //主串数组 Schars : array of AnsiChar; //字串数组 Dchars : array of AnsiChar; //获取模式数组 procedure GetNext; //查找匹配 function KPM(sPos:Integer):integer; public { Public declarations } end;var Form1: TForm1;implementation{$R *.dfm}{ TForm1 }procedure TForm1.GetNext;var len,m,n:Integer;begin m := 0; n := -1; len := Length(Dchars); SetLength(arrNext,len); arrNext[0] := -1; while (m+1)<= len do begin if (n = -1) or (Dchars[m] = Dchars[n]) then begin Inc(m); Inc(n); if (Dchars[m] <> Dchars[n]) then arrNext[m] := n else arrNext[m] := arrNext[n]; end else begin n := arrNext[n]; end; end;end;function TForm1.KPM(sPos:Integer): integer;var i,j:Integer;begin Result := 0; i := sPos; j := 0; while (i < Length(Schars)) and (j < Length(Dchars)) do begin if (Schars[i] = Dchars[j]) then begin Inc(i); Inc(j); end else begin Result := Result + j - arrNext[j]; if arrNext[j] <> -1 then begin j := arrNext[j]; end else begin j := 0; Inc(i); end; end; end; if j <> Length(Dchars) then Result := -1;end;procedure TForm1.Button1Click(Sender: TObject);var s,d:string; index : Integer;begin s := '*'; d := '人民'; index := -1; SetLength(Schars,Length(s)); SetLength(Dchars,Length(d)); Move(s[1],Schars[0],Length(s)); Move(d[1],Dchars[0],Length(d)); GetNext; index := KPM(0); if index = -1 then ShowMessage('没有找到匹配!') else ShowMessage('从第'+IntToStr(index+1)+'个字符开始匹配');end;end.

 

C#代码

using System;using System.Collections.Generic;using System.Text;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { string s = "abababaabab"; string p = "aaba"; int index = -1; index = KMP(s, p, 0); if (index != -1) Console.WriteLine("从第{0}个字符开始匹配", index + 1); else Console.WriteLine("{0}", "没有找到匹配"); } static void GetNext(string s, int[] next) { int m = 0; int n = -1; next[0] = -1; while (m + 1 < s.Length) { if (n == -1 || s[m] == s[n]) { ++m; ++n; if (s[m] != s[n]) next[m] = n; else next[m] = next[n]; } else { n = next[n]; } } } static int KMP(string sString, string dString, int pos) { int i = pos; int j = 0; int index = 0; int[] next = new int[dString.Length+1]; GetNext(dString, next); while (i < sString.Length && j < dString.Length) { if (sString[i] == dString[j]) { ++i; ++j; } else { index += j - next[j]; if (next[j] != -1) j = next[j]; else { j = 0; ++i; } } } next = null; if (j == dString.Length) return index; else return -1; } }}