Cod sursa(job #192969)

Utilizator Vlad2008Vlad VLD Vlad2008 Data 1 iunie 2008 19:05:43
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.15 kb
program potrivire;
const max=2000000;
var a,b:array [1..max] of char;
    f,g:text;
    sol:array [1..1000] of longint;
    p:array [1..max] of longint;
    i,j,n,m,nr:longint;
procedure prefix;
var k:longint;
begin
k:=0;
p[1]:=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 k:=k+1;
p[i]:=k;
end;
end;
procedure kmp;
var q:longint;
begin
q:=0;
nr:=0;
for i:=1 to m do begin
while (q>0) and (b[i]<>a[q+1]) do
q:=p[q];
if b[i]=a[q+1] then q:=q+1;
if q=n then begin
            nr:=nr+1;
            if nr<=1000 then sol[nr]:=i-n;
            q:=p[q];
            end;
end;
end;
begin
assign(f,'strmatch.in');
assign(g,'strmatch.out');
reset(f);
rewrite(g);
n:=0;
while not seekeoln(f) do begin
n:=n+1;
read(f,a[n]);
end;
readln(f);
if n<2000000 then
begin
m:=0;
while not seekeoln(f) do begin
m:=m+1;
read(f,b[m]);
end;
end
else m:=n;
if m<>n then begin
prefix;
kmp;
end;
if m<>n then begin
writeln(g,nr);
if nr>1000 then nr:=1000;
for i:=1 to nr do
write(g,sol[i],' ');
end
else begin
        writeln(g,1);
        write(g,0);
        end;
close(f);
close(g);
end.