Pagini recente » Cod sursa (job #1636791) | Cod sursa (job #492553) | Profil gabi2411 | Cod sursa (job #702644) | Cod sursa (job #298554)
Cod sursa(job #298554)
program kmp;
var a,b:array [1..2000000] of char;
f:array [1..2000000] of longint;
sol:array [1..1000] of longint
nrsol,i,k,m,n,q:longint;
function min(a,b:longint):longint;
begin
min:=a;
if b<a then
min:=b;
end;
begin
assign(input,'strmatch.in');
assign(output,'strmatch.out');
reset(input);
rewrite(output);
m:=0;
n:=0;
while not(eoln) do
begin
inc(m);
read(a[m]);
end;
readln;
while not(eoln) do
begin
inc(n);
read(b[n]);
end;
k:=0;
f[1]:=0;
nrsol:=0;
for q:= 2 to m do
begin
while (k>0) and (a[k+1] <> a[q]) do
k:=f[k];
if a[k+1] = a[q] then
inc(k);
f[q]:=k;
end;
q:=0;
for i:=1 to n do
begin
while (q>0) and (a[q+1] <> b[i]) do
q:=f[q];
if a[q+1] = b[i] then
inc(q);
if q = m then
begin
inc(nrsol);
if nrsol<=1000 then
sol[nrsol]:=i-m;
q:=f[q];
end;
end;
writeln(nrsol);
for i:=1 to min(nrsol,1000) do
write(sol[i],' ');
close(input);
close(output);
end.