Pagini recente » Cod sursa (job #1897031) | Cod sursa (job #2826797) | Cod sursa (job #1525749) | Cod sursa (job #1553062) | Cod sursa (job #302554)
Cod sursa(job #302554)
program kmp;
var a,b:array [1..2000002] of char;
nrsol,i,k,m,n:longint;
pi:array [1..2000002] of word;
sol:array [1..1000] of longint;
begin
assign(input,'strmatch.in');
assign(output,'strmatch.out');
reset(input);
rewrite(output);
readln(a);
readln(b);
i:=1;
while a[i]<>#0 do
inc(i);
m:=i-1;
i:=1;
while b[i]<>#0 do
inc(i);
n:=i-1;
k:=0;
pi[1]:=0;
for i:=2 to m do
begin
while (k>0) and (a[k+1]<>a[i]) do
k:=pi[k];
if a[k+1] = a[i] then
inc(k);
pi[i]:=k;
end;
k:=0;
for i:=1 to n do
begin
while (k>0) and (a[k+1]<>b[i]) do
k:=pi[k];
if a[k+1] = b[i] then
inc(k);
if k = m then
begin
inc(nrsol);
if nrsol<=1000 then
sol[nrsol]:=i-m;
k:=pi[k];
end;
end;
writeln(nrsol);
if nrsol>1000 then
nrsol:=1000;
for i:=1 to nrsol do
write(sol[i],' ');
close(input);
close(output);
end.