Pagini recente » Cod sursa (job #1612255) | Cod sursa (job #1714750) | Cod sursa (job #678588) | Cod sursa (job #2168409) | Cod sursa (job #422857)
Cod sursa(job #422857)
var a,b:array[0..2000000] of char;
k:array[0..2000000] of longint;
rez:array[0..1001] of longint;
n,l1,l2,i,r:longint;
c:char;
t:text;
procedure index_kmp(var b:array of char;l:longint);
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
for i:=2 to l do
begin
j:=k[i-1];
k[i]:=0;
repeat
begin
// writeln('if ',j+1,' ',i,' ',b[j+1],' ',b[i]);
if b[j+1]=b[i] then
begin
k[i]:=j+1;
break;
end
else j:=k[j];
end;
until j=0;
end;
end;
procedure kmp(var a,b:array of char;l1,l2:longint);
var i,j:longint;
begin
index_kmp(b,l2);
i:=1; j:=0;
while (i<=l1) do
begin
if b[j+1]=a[i] then
begin
i:=i+1;
j:=j+1; //au fost acceptate literele pana la pozitia j din stringul cautat
if j=l2 then
begin
n:=n+1;
if n<=1000 then rez[n]:=i-l2-1;
end;
end
else if j>0 then j:=k[j]
else i:=i+1;
end;
end;
begin
assign(t,'strmatch.in'); reset(t);
while (not(eoln(t))) do
begin
read(t,c);
l2:=l2+1;
b[l2]:=c;
// write(c);
end; // writeln;
readln(t);
while (not(eoln(t)) and not(eof(t))) do
begin
read(t,c);
l1:=l1+1;
a[l1]:=c;
// write(c);
end;
close(t); assign(t,'strmatch.out'); rewrite(t);
kmp(a,b,l1,l2);
//for i:=1 to l2 do writeln(i,'->',k[i]); readln;
writeln(t,n);
if n>1000 then
for i:=1 to 1000 do write(t,rez[i],' ')
else
for i:=1 to n do write(t,rez[i],' ');
close(t);
end.