Cod sursa(job #2405491)

Utilizator AlexNeaguAlexandru AlexNeagu Data 14 aprilie 2019 16:12:29
Problema Potrivirea sirurilor Scor 0
Compilator fpc Status done
Runda Arhiva educationala Marime 0.79 kb
program kmp;
type sir=array[0..2000000] of char;
     tabel=array[0..2000000] of longint;
var a,b:sir;
    urm,pos:tabel;
    n,m,r,i:longint;
    c:char;
procedure scanf(var s:sir; var n:longint);
begin
while not eoln do begin
read(c);
inc(n);
s[n]:=c;
end;
end;
procedure prefix();
var i,k:longint;
begin
urm[1]:=0;
k:=0;
for i:=2 to n do begin
while (k>0) and (a[i]<>a[k+1]) do k:=urm[k];
if (a[i]=a[k+1]) then inc(k);
urm[i]:=k;
end;
end;
procedure kmp();
var i,k:longint;
begin
k:=0;
for i:=1 to m do begin
while (k>0) and (b[i]<>a[k+1]) do k:=urm[k];
if (b[i]=a[k+1]) then inc(k);
if (k=n) then begin
inc(r);
pos[r]:=i-n;
k:=urm[k];
end;
end;
end;
begin
scanf(a,n);
readln;
scanf(b,m);
prefix();
kmp();
writeln(r);
for i:=1 to r do write(pos[i],' ');
end.