Pagini recente » Cod sursa (job #1808284) | Cod sursa (job #23979) | Cod sursa (job #2205965) | Cod sursa (job #1281083) | Cod sursa (job #170937)
Cod sursa(job #170937)
{ http://infoarena.ro/problema/strmatch }
{$LONGSTRINGS ON}
type vector=array[1..2000000] of longint;
var a,b:string;
nr,nb,na:longint;
lim,i:word;
v,pi:vector;
f,g:text;
{ Algoritmul === Knuth-Morris-Pratt === }
procedure prefix;
var i,k:longint;
begin
k:=0;
pi[1]:=0;
for i:=2 to na do
begin
while (k>0) and (a[i]<>a[k+1]) do
k:=pi[k];
if a[k+1]=a[i] then k:=k+1;
pi[i]:=k;
end;
end;
procedure kmp;
var i,k:longint;
begin
k:=0;
for i:=1 to nb do
begin
while (k>0) and (a[k+1]<>b[i]) do
k:=pi[k];
if a[k+1]=b[i] then inc(k);
if k=na then begin
inc(nr);
if nr<=1000 then v[nr]:=i-na;
k:=pi[k];
end;
end;
end;
{ ===== Sfasit cautare ===== }
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
readln(f,a);
read(f,b);
na:=length(a);
nb:=length(b);
if na>nb then writeln(g,0)
else begin
prefix;
kmp;
writeln(g,nr);
if nr>1000 then lim:=1000
else lim:=nr;
for i:=1 to lim do write(g,v[i],' ');
end;
close(f); close(g);
end.