Pagini recente » Cod sursa (job #705298) | Cod sursa (job #2656651) | Cod sursa (job #1212361) | Cod sursa (job #982335) | Cod sursa (job #177823)
Cod sursa(job #177823)
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 (a[n]>='A')and(a[n]<='Z') do
inc(n);
dec(n);
m:=1;
while (b[m]>='A')and(b[m]<='Z') 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.