Cod sursa(job #168933)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 31 martie 2008 21:26:10
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 1.11 kb
program kmpre;
var A,B : array [1..2000000] of string[1];
    p : array [1..2000000] of longint;
    sol : array [1..1000] of longint;
    m,n,i,k,nr,q : longint;
    f,g : text;

procedure pi;
begin
k := 0;
p[1] := 0;
for i := 2 to n do begin
        while (k>0) and (A[i]<>A[k+1]) do
        k := p[k];
        if A[k+1]=A[i] then k := k+1;
        p[i] := k;
        end;
end;



procedure kmp;
begin
nr := 0;
q := 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');
reset(f);
assign(g,'strmatch.out');
rewrite(g);

n := 0;
while not eoln(f) do begin
        n := n+1;
        read(f,A[n]);
        end;
readln(f);
m := 0;
while not eoln(f) do begin
        m := m+1;
        read(f,B[m]);
        end;

pi;
kmp;

for i := 1 to n do
write(p[i],' ');
readln;

write(nr);

for i := 1 to nr do
write(sol[i],' ');
readln;


end.