KMP算法【fengyunfly吧】

fengyunfly吧关注：9贴子：102

5回复贴，共1页

KMP算法

program kmp;
var re,c,d,e,f,g,h,i,j,k:longint;
    s,t,r:string;
    next:array[1.. 10000] of longint;
procedure getnext;
var i,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 index(p,q:string):longint;
var i,j:longint;
begin
  getnext;
  index:=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];
  end;
  if j>length(t) then index:=i-length(t);
end;

begin
  fillchar(next,sizeof(next),0);
  readln(s);
  readln(t);
  re:=index(s,t);
  if re>0 then begin
    writeln(re);
  end
  else begin
    writeln('Error');
  end;
end.

送TA礼物

IP属地:上海

1楼2008-06-17 20:30回复

index不用带参吧。。�

IP属地:上海

2楼2008-06-20 21:10

my kmp

var s,p:ansistring;
pre:array[1..100000] of longint;
procedure prefix;
var len,k,i:longint;
begin
len:=length(p);
pre[1]:=0;
k:=0;
for i:=2 to len do
begin
while (k>0)and(p[k+1]<>p[i]) do k:=pre[k];
if p[k+1]=p[i] then
begin
inc(k);
pre[i]:=k;
end;
end;
end;
procedure print(k:longint);
var i:longint;
begin
writeln(s);
for i:=1 to k do write(' ');
writeln(p);
end;
procedure match;
var lens,lenp,i,k:longint;
begin
lens:=length(s); lenp:=length(p);
k:=0;
for i:=1 to lens do
begin
while (k>0)and(s[i]<>p[k+1]) do k:=pre[k];
if s[i]=p[k+1] then inc(k);
if k=lenp then begin writeln(i-lenp); print(i-lenp); k:=pre[k]; end;
end;
end;
begin
readln(s);
readln(p);
prefix;
match;
end.

IP属地:中国香港

3楼2008-06-21 11:44

var len,i,j:longint;
s1,s2:string;
next:array[0..10000]of longint;
begin
readln(s1);
readln(s2);
next[1]:=0;
for i:=2 to length(s1) do
begin
j:=i-1;
while (s1[next[j]+1]<>s1[i]) and (j<>0) do j:=next[j];
if j<>0 then next[i]:=next[j]+1 else next[i]:=0;
end;
len:=1;
for i:=1 to length(s2) do
begin
while (s2[i]<>s1[len]) and (len<>1) do
begin len:=next[len-1]+1; end;
if s2[i]=s1[len] then inc(len);
if len>length(s1) then begin
writeln(i-len+2);
writeln(pos(s1,s2));
readln;
exit;
end;
end;
writeln('failed');
writeln(pos(s1,s2));
readln;
end.

IP属地:上海

4楼2008-06-23 17:47

哇塞

IP属地:福建

5楼2008-08-10 22:21

这个
program kmp;
var c,d,e,f,g,h,i,j,k,m,n:longint;
p:array[1.. 100] of longint;
a,b:string;
begin
readln(a);
readln(b);
p[1]:=0;
j:=0;
for i:=2 to length(b) do begin
while (j>0) and (b[j+1]<>b[i]) do j:=p[j];
if b[j+1]=b[i] then inc(j);
p[i]:=j;
end;
j:=0;
for i:=1 to length(a) do begin
while (j>0) and (b[j+1]<>a[i]) do j:=p[j];
if b[j+1]=a[i] then inc(j);
if j=length(b) then begin
writeln(i-length(b)+1);
halt;
end;
end;
writeln('No solution');
end.

IP属地:上海

7楼2009-02-04 20:22

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

贴吧热议榜

5回复贴，共1页

<返回fengyunfly吧

发表回复

发贴请遵守贴吧协议及“七条底线”贴吧投诉

内容:

使用签名档查看全部

发表

保存至快速回贴

日	一	二	三	四	五	六

KMP算法

登录百度账号

扫二维码下载贴吧客户端