fengyunfly吧 关注:9贴子:102
  • 1回复贴,共1
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.


IP属地:上海1楼2008-06-17 20:30回复
    这个
    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
    回复