Pagini recente » Cod sursa (job #2962796) | Cod sursa (job #2800124) | Cod sursa (job #1491769) | Cod sursa (job #1275377) | Cod sursa (job #423022)
Cod sursa(job #423022)
var p,t:array[0..2000001] of char;
i,j,l1,l2,n:longint;
k:array[0..2000001] of longint;
rez:array[0..1011] of longint;
te:text;
procedure kmp_index(var p:array of char; var l:longint);
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
i:=1; read(te,p[i]);
while(not(eoln(te))) do
begin
i:=i+1; read(te,p[i]);
j:=k[i-1];
k[i]:=0;
repeat
if p[j+1]=p[i] then
begin
k[i]:=j+1;
break;
end
else
begin
if j=0 then break;
j:=k[j];
end;
until 1=2;
end;
l:=i;
end;
procedure kmp_search(var p,t:array of char;l1,l2:longint);
var i,j:longint;
begin
if l1=l2 then
begin
n:=1;
rez[1]:=0;
exit;
end;
i:=1; j:=0;
while (i<=l2) do
begin
if t[i]=p[j+1] then
begin
j:=j+1;
i:=i+1;
if j=l1 then
begin
n:=n+1;
if n<=1000 then rez[n]:=i-l1-1;
end;
end
else if j>0 then j:=k[j]
else i:=i+1;
end;
end;
begin
assign(te,'strmatch.in'); reset(te);
kmp_index(p,l1);
readln(te);
while(not(eoln(te))and not(eof(te))) do
begin
l2:=l2+1;
read(te,t[l2]);
end;
close(te);
assign(te,'strmatch.out'); rewrite(te);
kmp_search(p,t,l1,l2);
writeln(te,n);
if n>1000 then n:=1000;
for i:=1 to n do write(te,rez[i],' ');
close(te);
end.