首页 > 代码库 > KMP与扩展KMP初探

KMP与扩展KMP初探

2024-07-18 00:29:21   217人阅读

KMP

KMP算法主要用于字符串匹配中的单串匹配

next函数：表示当前字符失配时，应从模式串的第几位开始匹配（越大越好）。即模式串的前缀与以t[i]为结尾的后缀的最长相同部分的长度。

代码如下（pascal）

var        s,t:string;        next,ans:array[0..100] of longint;        i,j:longint;begin        readln(s);        readln(t);        next[1]:=0;        {构造next}        j:=0;        for i:=2 to length(t) do        begin                while (j>0)and(t[j+1]<>t[i]) do j:=next[j]; {失配}                if t[j+1]=t[i] then j:=j+1;                next[i]:=j;        end;        {KMP主程序}        j:=0;        for i:=1 to length(s) do        begin                while (j>0)and(t[j+1]<>s[i]) do j:=next[j]; {失配}                if t[j+1]=s[i] then j:=j+1;                if j=length(t) then                         {找到匹配}                begin                        inc(ans[0]);                        ans[ans[0]]:=i-length(t)+1;                        j:=next[j];                end;        end;        for i:=0 to ans[0] do         writeln(ans[i]);end.

扩展KMP

顾名思义就是KMP算法的扩展，其可以求出以s[i]为开始的字符串，与t的最长公共前缀。

扩展KMP的next函数：表示以t[i]为开始的字符串，与t的最长公共前缀的长度。

扩展KMP的extend函数：表示以s[i]为开始的字符串，与t的最长公共前缀的长度。

代码如下（pascal）

var        s,t:ansistring;        i,j,k,p,l,n,m:longint;        next,extened:array[0..1000] of longint;begin        readln(s);        readln(t);        n:=length(s);        m:=length(t);        s:=s+‘@‘;    {防越界}        t:=t+‘#‘;    {防越界}        {构造next}        j:=0;        while T[1+j]=T[2+j] do inc(j);        next[2]:=j;        k:=2;        for i:=3 to m do        begin                p:=k+next[k]-1;        {p为最远的已比较过的点}                l:=next[i-k+1];        {l为t与t[i-k+1..m]的LCP}                if l+i-1<p then next[i]:=l                else begin                        if p-i+1>0 then j:=p-i+1 else j:=0;                        while T[i+j]=T[1+j] do inc(j);                        next[i]:=j;                        k:=i;          {更新k}                end;        end;        {Extened_KMP主程序}        j:=0;        while T[1+j]=S[1+j] do inc(j);        extened[1]:=j;        k:=1;        for i:=2 to n do        begin                p:=k+extened[k]-1;     {p为最远的已比较过的点}                l:=next[i-k+1];        {l为t与t[i-k+1..m]的LCP}                if l+i-1<p then extened[i]:=l                else begin                        if p-i+1>0 then j:=p-i+1 else j:=0;                        while S[i+j]=T[1+j] do inc(j);                        extened[i]:=j;                        k:=i;          {更新k}                end;        end;        for i:=1 to n do         writeln(extened[i]);end.


联系
我们