program KMP;
var
next:array[1..500000]of longint;
s1,s2:ansistring;
ii:longint;
procedure getnext(t:ansistring);
var
j,k:longint;
begin
j:=1; k:=0;
while j<Length(t) do
begin
if (k=0)or(t[j]=t[k]) then begin inc(j); inc(k); next[j]:=k; end else k:=next[k];
end;
end;
function find(s:ansistring;t:ansistring):longint;
var
i,j:longint;
begin
getnext(t);
find:=0;
i:=1; j:=1;
while (i<=Length(s)) and (j<=Length(t)) do
begin
if (j=0)or(s[i]=t[j]) then begin inc(i); inc(j); end else j:=next[j]; if j>length(t) then find:=i-Length(t);
end;
end;
begin
write('s=');
readln(s1);
write('t=');
readln(s2);
ii:=find(s1,s2);
if ii<>0 then begin writeln('Found ',s2,' in ',s1,' at ',ii); end else Writeln('Cannot find ', s2,' in ',s1);
end.
其实是百度百科上的我改了一下= =

真-不丑

推荐matrix67

我突然发现67大神的与算法导论上的KMP一样、除了变量名
- -

不是我想说它丑
kmp 也能写成这个样子、、、、、、

我表示、经过我的极限缩行、KMP竟然可以缩到4行、、只有4个for语句了、、

next[1] = 0;
for (i = 2,j = 0; i < m; ++i)
{
for (; j && a[j+1] != a[i]; j = next[j]);
j += a[j+1] == a[i];
next[i] = j;
}

你是有多丑、、
for (i=2,j=0;st1[i];next[i]=st1[j+1]==st1[i]?++j:0,i++)
for (;j&&st1[j+1]!=st1[i];j=next[j]);

- -
还是正常点的才好看

喂、这个是极其正常的了、标准的for语句、