Pagini recente » Cod sursa (job #751668) | Cod sursa (job #666742) | Cod sursa (job #3292624) | Cod sursa (job #330165) | Cod sursa (job #166018)
Cod sursa(job #166018)
program strmatch;
const
fin='strmatch.in';
fout='strmatch.out';
nmax=2000000;
type
chararray=array[0..nmax] of char;
pchararray=^chararray;
var
a,b:pchararray;
t:array[0..nmax] of longint;
meci:array[1..1001] of longint;
i,j,k,n,m,nr:longint;
function min(x,y:longint):longint;
begin
if x<y then
min:=x
else
min:=y;
end;
procedure citeste(var a:pchararray;var l:longint);
begin
l:=0;
new(a);
while not(seekeoln(input)) do
begin
inc(l);
read(a^[l]);
end;
readln;
end;
procedure prefix;
var
k,q:longint;
begin
t[1]:=0;
k:=0;
for q:=2 to m do
begin
while (k>0) and (a^[q]<>a^[k+1]) do
k:=t[k];
if a^[q]=a^[k+1] then
inc(k);
t[q]:=k;
end;
end;
procedure kmp;
var
k,i:longint;
begin
prefix;
k:=0;
for i:=1 to n do
begin
while (k>0) and (b^[i]<>a^[k+1]) do
k:=t[k];
if (b^[i]=a^[k+1]) then
inc(k);
if k=m then
begin
inc(nr);
if nr<1001 then
meci[nr]:=i-m+1;
k:=t[k];
end;
end;
end;
begin
assign(input,fin);
reset(input);
citeste(a,m);citeste(b,n);
close(input);
assign(output,fout);
rewrite(output);
kmp;
writeln(nr);
for i:=1 to min(nr,1000) do
write(meci[i]-1,' ');
close(output);
end.