Cod sursa(job #167504)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 29 martie 2008 17:30:55
Problema Prefix Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.26 kb
program strmatch;
var A,B : array [1..2000000] of char;
    p : array [1..20000000] of longint;
    sol : array [1..1000] of longint;
    m,n,i,nr : longint;
    f,g : text;

procedure pi;
var k : longint;
begin
k := 0;

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

if A[i]=A[k+1] then k := k+1;

p[i] := k;
end;
end;


procedure kmp;
var k : longint;
begin
k := 0;
nr := 0;

for i := 1 to m do begin
while (k>0) and (B[i]<>A[k+1]) do
k := p[k];

if B[i]=A[k+1] then k := k+1;

if k=n then begin
            nr := nr+1;
            if nr<=1000 then sol[nr] := i-n;
            k := p[k];
            end;


end;
end;

begin
assign(f,'strmatch.in');
reset(f);
assign(g,'strmatch.out');
rewrite(g);

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

{fillchar(A,sizeof(A),'a');
}
readln(f,a);
n := sizeof(A);

{fillchar(B,sizeof(B),' ');
}
readln(f,B);
m := sizeof(B);


pi;

kmp;

writeln(g,nr);

if nr<1000 then for i := 1 to nr do
                write(g,sol[i],' ')
           else for i := 1 to 1000 do
                write(g,sol[i],' ');

close(f);
close(g);


end.