Cod sursa(job #166677)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 28 martie 2008 12:26:01
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.99 kb
var p:array[0..2000000] of longint;
    sol:array[0..200000] of longint;
    a,b:array[1..2000000] of char;
    n,m,i:longint;
    f,g:text;

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

procedure kmp;
 var i,k:longint;
 begin
  pi; sol[0]:=0;
  k:=0;
  for i:=1 to m do begin
   while (k<>0) and (b[i]<>a[k+1]) do
    k:=p[k];
   if b[i]=a[k+1] then
    inc(k);
   if k=n then begin
    inc(sol[0]);
    sol[sol[0]]:=i-n;
    k:=p[k];
   end;
  end;
 end;

begin
 assign(f,'strmatch.in'); reset(f);
 assign(g,'strmatch.out'); rewrite(g);
 n:=0; m:=0;
 while not(eoln(f)) do begin
  inc(n);
  read(f,a[n]);
 end;
 readln(f);
 while not(eoln(f)) do begin
  inc(m);
  read(f,b[m]);
 end;
 kmp;
 writeln(g,sol[0]);
 if sol[0]>1000 then
  sol[0]:=1000;
 for i:=1 to sol[0] do
  write(g,sol[i],' ');
 close(f); close(g);
end.