Cod sursa(job #166666)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 28 martie 2008 12:11:21
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.94 kb
var p,sol:array[0..2000010] of longint;
    a,b:ansistring;
    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);
 readln(f,a);
 readln(f,b);
 n:=length(a);
 m:=length(b);
 kmp;
 if sol[0]<>0 then
  writeln(g,sol[0]);
 if sol[0]>1000 then
  sol[0]:=1000;
 for i:=1 to sol[0]-1 do
  write(g,sol[i],' ');
 if sol[0]<>0 then
  writeln(g,sol[sol[0]])
 else
  writeln(g,0);
 close(f); close(g);
end.