Pagini recente » Cod sursa (job #841155) | Cod sursa (job #2301224) | Cod sursa (job #682610) | Cod sursa (job #2091713) | Cod sursa (job #1402823)
//KMP ^_^.
program kmp;
const lungmax = 2000001;
pozitii = 1001;
var f,g:text;
bufin,bufout:array[1..1 shl 17] of char;
T, P:ansistring;
urm:array[1..lungmax] of longint;
v:array[1..pozitii] of longint;
n,m,i,q,k:longint;
//----------------------------
procedure urmatorul(p:ansistring);
var k,m,q:longint;
begin
m := length(p);
urm[1] := 0;
k := 0;
for q := 2 to m do
begin
while (k > 0) and (p[k+1] <> p[q]) do k := urm[k];
if p[k+1] = p[q] then inc(k);
urm[q] := k;
end;
end;
//---------------------------
procedure swap(var x,y:ansistring);
var aux:ansistring;
begin
aux := x; x := y; y := aux;
end;
//---------------------------
procedure adauga(x:longint);
begin
inc(k); v[k]:=x;
end;
begin
assign(f,'strmatch.in'); reset(f);
assign(g,'strmatch.out'); rewrite(g);
settextbuf(f,bufin); settextbuf(f,bufout);
readln(f,T); readln(f,P); swap(T, P);
n := length(t);
m := length(p);
urmatorul(P);
q := 0; k :=0;
for i := 1 to n do
begin
while (q > 0) and (p[q+1] <> t[i]) do q := urm[q];
if p[q+1] = t[i] then inc(q);
if q = m then
begin
// writeln(g,i-m);
if k < 1000 then adauga(i-m)
else inc(k);
q := urm[q];
end;
end;
writeln(g,k);
if k > 1000 then
k:=1000;
for i := 1 to k do
write(g,v[i],' ');
close(f); close(g);
end.