Cod sursa(job #153896)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 10 martie 2008 19:51:58
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.12 kb
program potrivire_siruri;
var a,b:array[0..2000001]of char;
    pi:array[0..2000001]of Longint;
    poz:array[1..1001]of Longint;
    n,m,nr,i:Longint;
    f:text;
procedure prefix;
var 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 k:=k+1;
 pi[i]:=k;
 end;
end;
procedure kmp;
var q:longint;
begin
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 q:=q+1;
 if q=n then begin
             inc(nr);
             if nr<=1000 then poz[nr]:=i-n+1;
             q:=pi[n];
             end;
 end;
end;
begin
assign(f,'strmatch.in');reset(f);
n:=0;
while not eoln(f) do begin
                     n:=n+1;
                     read(f,a[n]);
                     end;
readln(f);
m:=0;
while (not eoln(f))or(not eof(f)) do begin
                     m:=m+1;
                     read(f,b[m]);
                     end;
close(f);
prefix;
kmp;
assign(f,'strmatch.out');rewrite(f);
writeln(f,nr);
if nr>1000 then nr:=1000;
for i:=1 to nr do write(f,poz[i],' ');
close(f);
end.