Cod sursa(job #177828)

Utilizator CezarMocanCezar Mocan CezarMocan Data 13 aprilie 2008 17:22:59
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.88 kb
var a,b:array[1..2000100] of char;
    pi:array[0..2000100] of longint;
    rez:array[1..1010] of longint;
    n,m,i,j,x,nr:longint;

begin
assign(input,'strmatch.in');reset(input);
assign(output,'strmatch.out');rewrite(output);
readln(b);
readln(a);
n:=1;
while (ord(a[n])<>0) do
        inc(n);
dec(n);
m:=1;
while (ord(b[m])<>0) do
        inc(m);
dec(m);
pi[0]:=-1;
pi[1]:=0;
//prefix
for i:=2 to m do
        begin
        x:=pi[i-1];
        if b[x+1]=b[i] then
                pi[i]:=x+1
        else
                begin
                while x>=0 do
                        begin
                        x:=pi[x];
                        if x<0 then
                                break;
                        if b[x+1]=b[i] then
                                begin
                                pi[i]:=x+1;
                                break;
                                end;
                        end;
                end;
        end;
//KMP
x:=0;
for i:=1 to n do
        begin
        if a[i]=b[x+1] then
                inc(x)
        else
                begin
                while x>=0 do
                        begin
                        x:=pi[x];
                        if x<0 then
                                break;
                        if b[x+1]=a[i] then
                                begin
                                inc(x);
                                break;
                                end;
                        end;
                end;
        if x=m then
                begin
                inc(nr);
                if nr<=1000 then
                        rez[nr]:=i-m;
                end;
        if x<0 then
                x:=0;
        end;
writeln(nr);
if nr>1000 then
        nr:=1000;
for i:=1 to nr do
        write(rez[i],' ');
close(input);close(output);
end.