Pagini recente » Cod sursa (job #2937415) | Cod sursa (job #1476881) | Cod sursa (job #3141174) | Cod sursa (job #1063686) | Cod sursa (job #701489)
Cod sursa(job #701489)
program kmp;{potrivire siruri}{primele 1000 solutii}
var x,y:ansistring;
bufferin,bufferout:array[1..65000] of byte;
pi:array[1..2000000] of longint;
d:array[1..1000] of longint;
i,k,n,m,contor:longint;
f,g:text;
procedure constructie_pi;
var i,k:integer;
begin
k:=0;
pi[1]:=0;{pi[i]<i => pi[1]=0}
for i:=2 to m do
begin
while (k>0) and (x[i]<>x[k+1]) do {cat timp prefixul nu este nul si literele}
k:=pi[k]; {nu coincid sar din K in Pi[K]}
if (x[i]=x[k+1]) then {daca literele coincid}
inc(k);
pi[i]:=k;
end;
end;
begin
assign(f,'strmatch.in');
assign(g,'strmatch.out');
reset(f);
settextbuf(f,bufferin);
rewrite(g);
settextbuf(f,bufferout);
readln(f,x);
readln(f,y);
n:=length(y);
m:=length(x);
constructie_pi;
k:=0;
for i:=1 to n do
begin
while (k>0) and (y[i]<>x[k+1]) do{cat timp prefixul nu este nul si literele}
k:=pi[k];{nu coincid sar din K in Pi[K]}
if y[i]=x[k+1] then
inc(k);
{d[i]:=k;}
if k=m then
begin
inc(contor);
if contor<1001 then
d[contor]:=i-k;
k:=pi[k];{cand k ajunge la m il reinitializez cu pi[k]!!!!!!}
end;
end;
writeln(g,contor);
if contor>1000 then
contor:=1000;
for i:=1 to contor do
write(g,d[i],' ');
close(f);
close(g);
end.