Cod sursa(job #404841)

Utilizator nickyyLal Daniel Emanuel nickyy Data 26 februarie 2010 19:34:54
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.17 kb
const infile='strmatch.in';
  outfile='strmatch.out';
  maxn=2000003;
  maxs=1003;
var a,b:array[1..maxn]of char;
  pi:array[1..maxn]of longint;
  s:array[1..maxs]of longint;
  n,m,nr:longint;

 procedure citire;
 begin
   assign(input,infile); reset(input);
   n:=0; while not eoln(input) do begin inc(n); read(a[n]); end;
   readln;
   m:=0; while not eoln(input) do begin inc(m); read(b[m]); end;
   close(output);
 end;

 procedure prefix;
 var j,k:longint;
 begin
   pi[1]:=0; k:=0;
   for j:=2 to n do begin
     while(k>0)and(a[k+1]<>a[j])do k:=pi[k];
     if(a[k+1]=a[j])then inc(k);
     pi[j]:=k;
     end;
 end;

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

 procedure scrie;
 var i:longint;
 begin
   assign(output,outfile); rewrite(output);
   writeln(nr);
   if(nr>1000)then nr:=1000;
   for i:=1 to nr do write(s[i],' ');
   close(output);
 end;

begin
  citire; KMP; scrie;
end.