Pagini recente » Cod sursa (job #658538) | Cod sursa (job #2021497) | Cod sursa (job #2015746) | Cod sursa (job #202335) | Cod sursa (job #423025)
Cod sursa(job #423025)
var p: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;
c:char;
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: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; read(te,c);
while (not(eoln(te)) and not(eof(te))) do
begin
if c=p[j+1] then
begin
j:=j+1;
i:=i+1; read(te,c);
if j=l1 then
begin
n:=n+1;
if n<1001 then rez[n]:=i-l1-1;
end;
end
else if j>0 then j:=k[j]
else begin i:=i+1; read(te,c); end;
end;
if (p[j+1]=c) and (j+1=l1) then
begin
n:=n+1;
if n<1001 then rez[n]:=j+1;
end;
end;
begin
assign(te,'strmatch.in'); reset(te);
kmp_index(p,l1);
readln(te);
kmp_search(p,l1,l2);
close(te);
assign(te,'strmatch.out'); rewrite(te);
writeln(te,n);
if n>1000 then n:=1000;
for i:=1 to n do write(te,rez[i],' ');
close(te);
end.