Pagini recente » Cod sursa (job #589935) | Cod sursa (job #1868719) | Cod sursa (job #562565) | Cod sursa (job #1629590) | Cod sursa (job #416671)
Cod sursa(job #416671)
program kmp;
var f, g:text;
p,t:array[1..2000000] of char;
l, poz:array[1..1000] of longint;
m, n, nr:longint;
procedure citire;
begin
while not seekeoln(f) do
begin
m:=m+1;
read(f,p[m]);
end;
readln(f);
while not seekeoln(f) do
begin
n:=n+1;
read(f,t[n]);
end;
end;
procedure prefix;
var k, i:longint;
begin
k:=0;
l[1]:=0;
for i:=2 to m do
begin
k:=l[i-1];
while (k>0) and (p[k+1]<>p[i]) do
k:=l[k];
if p[k+1]=p[i] then
k:=k+1;
l[i]:=k;
end;
end;
procedure rezolvare;
var k, i:longint;
begin
k:=0;
for i:=1 to n do
begin
while (k>0) and (t[i]<>p[k+1]) do
k:=l[k];
if t[i]=p[k+1] then
k:=k+1;
if k=m then
begin
nr:=nr+1;
if nr<=1000 then
poz[nr]:=i-m;
k:=l[k];
end;
end;
end;
procedure afisare;
var i:longint;
begin
writeln(g,nr);
if nr>1000 then
nr:=1000;
for i:=1 to nr do
write(g,poz[i],' ');
end;
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
citire;
prefix;
rezolvare;
afisare;
close(f);
close(g);
end.