Cod sursa(job #670482)

Utilizator pongraczlajosLajos Pongracz pongraczlajos Data 29 ianuarie 2012 12:26:50
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.88 kb
var a,b:array[1..2000005] of char;
    pi:array[0..2000005] of longint;
    x:array[1..1005] of longint;
    n,m,k,i,q:longint;
    f:text;

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

begin
assign(f,'strmatch.in');
reset(f);
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;
close(f);

prefix;
k:=0;
q:=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(k);
         if k<=1000 then x[k]:=i-n;
        end;
end;

assign(f,'strmatch.out');
rewrite(f);
writeln(f,k);
if k>1000 then k:=1000;
for i:=1 to k do write(f,x[i],' ');
close(f);
end.