Pagini recente » Cod sursa (job #1318840) | Cod sursa (job #1717839) | Cod sursa (job #2023603) | Cod sursa (job #200489) | Cod sursa (job #177828)
Cod sursa(job #177828)
var a,b:array[1..2000100] of char;
pi:array[0..2000100] of longint;
rez:array[1..1010] of longint;
n,m,i,j,x,nr:longint;
begin
assign(input,'strmatch.in');reset(input);
assign(output,'strmatch.out');rewrite(output);
readln(b);
readln(a);
n:=1;
while (ord(a[n])<>0) do
inc(n);
dec(n);
m:=1;
while (ord(b[m])<>0) do
inc(m);
dec(m);
pi[0]:=-1;
pi[1]:=0;
//prefix
for i:=2 to m do
begin
x:=pi[i-1];
if b[x+1]=b[i] then
pi[i]:=x+1
else
begin
while x>=0 do
begin
x:=pi[x];
if x<0 then
break;
if b[x+1]=b[i] then
begin
pi[i]:=x+1;
break;
end;
end;
end;
end;
//KMP
x:=0;
for i:=1 to n do
begin
if a[i]=b[x+1] then
inc(x)
else
begin
while x>=0 do
begin
x:=pi[x];
if x<0 then
break;
if b[x+1]=a[i] then
begin
inc(x);
break;
end;
end;
end;
if x=m then
begin
inc(nr);
if nr<=1000 then
rez[nr]:=i-m;
end;
if x<0 then
x:=0;
end;
writeln(nr);
if nr>1000 then
nr:=1000;
for i:=1 to nr do
write(rez[i],' ');
close(input);close(output);
end.