Pagini recente » Cod sursa (job #1818132) | Cod sursa (job #1025924) | Cod sursa (job #678779) | Cod sursa (job #2590740) | Cod sursa (job #167572)
Cod sursa(job #167572)
program kmp;
var A,B : array [1..2000000] of char;
p : array [1..2000000] of longint;
sol : array [1..1000] of longint;
m,n,i,nr : longint;
f,g : text;
ok : boolean;
procedure pi;
var k : longint;
begin
k := 0;
for i := 2 to n do begin
while (k>0) and (A[i]<>A[k+1]) do
k := p[k];
if A[i]=A[k+1] then k := k+1;
p[i] := k;
end;
end;
procedure km;
var k : longint;
begin
k := 0;
nr := 0;
for i := 1 to m do begin
while (k>0) and (B[i]<>A[k+1]) do
k := p[k];
if B[i]=A[k+1] then k := k+1;
if k=n then begin
nr := nr+1;
if nr<=1000 then Sol[nr] := i-n;
k := p[k];
end;
end;
end;
begin
assign(f,'strmatch.in');
reset(f);
assign(g,'strmatch.out');
rewrite(g);
n := 0;
while not seekeoln(f) do begin
n := n+1;
read(f,A[n]);
end;
m := 0;
readln(f);
while not seekeoln(f) do begin
m := m+1;
read(f,B[m]);
end;
if n<>m then begin
pi;
km;
writeln(g,nr);
if nr>1000 then nr := 1000;
for i := 1 to nr do
write(g,sol[i],' ');
end
else begin
writeln(g,1);
writeln(g,0);
end;
close(f);
close(g);
end.