Pagini recente » Cod sursa (job #2521198) | Cod sursa (job #1907052) | Cod sursa (job #889013) | Cod sursa (job #857310) | Cod sursa (job #170683)
Cod sursa(job #170683)
{ http://infoarena.ro/problema/strmatch }
{$LONGSTRINGS ON}
type vector=array[1..10000] of longint;
var a,b:string;
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:vector;
i,j,m,n: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);
if length(a)>length(b) then writeln(g,0)
else begin
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],' ');
end;
close(f); close(g);
end.