Pagini recente » Cod sursa (job #757383) | Cod sursa (job #2909723) | Cod sursa (job #16684) | Cod sursa (job #2441398) | Cod sursa (job #170681)
Cod sursa(job #170681)
{ http://infoarena.ro/problema/strmatch }
type vector=array[1..1000000] of longint;
var a,b:string;
n,k:longint;
lim,i:word;
v:vector;
f,g:text;
{ Algoritmul === Knuth-Morris-Pratt === }
procedure cauta(a,b:string;var v:vector;var k:longint);
var
pi:array[1..1000]of longint;
i,j,m,n,rez:longint;
procedure prefix;
var k,i:longint;
begin
m:=length(a);
k:=0; pi[1]:=0;
for i:=2 to m do
begin
while (k>0) and (a[i]<>a[k]) do
k:=pi[k];
if a[k+1]=a[i] then k:=k+1;
pi[i]:=k;
end;
end;
begin
m:=length(a); n:=length(b);
j:=0; k:=0;
prefix;
for i:=1 to n do
begin
while (j>0) and (a[j+1]<>b[i]) do
j:=pi[j];
if a[j+1]=b[i] then j:=j+1;
if j=m then begin
inc(k);
if k<1000 then v[k]:=i-m+1;
end;
end;
end;
{ ===== Sfasit cautare ===== }
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
readln(f,a);
read(f,b);
cauta(a,b,v,k);
writeln(g,k);
if k>1000 then lim:=1000
else lim:=k;
for i:=1 to lim do write(g,v[i],' ');
close(f); close(g);
end.