Cod sursa(job #295591)

Utilizator punkistBarbulescu Dan punkist Data 3 aprilie 2009 14:26:29
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.59 kb
var solutii,m,n:longint;
    a,b:array[0..2000005] of char;
    pi:array[0..2000005] of longint;
    pos:array[1..1024] of longint;

procedure Citeste;
 var f:file;
     numread:longint;
     buf:array[1..4000020] of char;
     i,temp:int64;
 begin
  assign(f,'strmatch.in');
  reset(f,1);
  repeat
   begin
    blockread(f,buf,sizeof(buf),numread);
    writeln(numread);
   end;
  until numread=0;{
  close(f);
  m:=0;n:=0;
  while ord(buf[m+1])>20 do
   begin
    m:=m+1;
    a[m]:=buf[m];
   end;
  i:=0;
  while ord(buf[m+i+1])<20 do i:=i+1;
  i:=m+i;
  while ord(buf[temp+1])>20 do
   begin
   n:=n+1;
   temp:=i+n;
   b[n]:=buf[temp];
   end;               }
  a[0]:=' ';b[0]:=' ';
 end;

procedure make_prefix;
 var i,q:longint;
 begin
  q:=0;
  pi[1]:=0;
  for i:=2 to m do
   begin
    while (q<>0) and (a[q+1] <> a[i]) do q:=pi[q];
    if A[q+1] = A[i] then q:=q+1;
    pi[i]:=q;
   end;
 end;

procedure KMP;
 var i,q:longint;
 begin
  q:=0;
  solutii:=0;
  for i:=1 to n do
   begin
    while (q<>0) and (a[q+1] <> b[i]) do q := pi[q];
    if (A[q+1] = b[i]) then q:=q+1;
    if (q=M) then
     begin
      q:=pi[m];
      solutii:=solutii+1;
      if (solutii <= 1000) then pos[solutii] := i-m;
     end;
   end;
 end;

procedure Scrie;
 var i,min:longint;
     f:text;
 begin
  if solutii<1000 then min:=solutii
  else min:=1000;
  assign(f,'strmatch.out');
  rewrite(f);
  writeln(f,solutii);
  for i:=1 to min do
   begin
    write(f,pos[i],' ');
   end;
  close(f);
 end;
begin
Citeste;
Make_Prefix;
KMP;
Scrie;
end.