Pagini recente » Cod sursa (job #1490644) | Cod sursa (job #2836992) | Cod sursa (job #3187625) | Cod sursa (job #2193489) | Cod sursa (job #404841)
Cod sursa(job #404841)
const infile='strmatch.in';
outfile='strmatch.out';
maxn=2000003;
maxs=1003;
var a,b:array[1..maxn]of char;
pi:array[1..maxn]of longint;
s:array[1..maxs]of longint;
n,m,nr:longint;
procedure citire;
begin
assign(input,infile); reset(input);
n:=0; while not eoln(input) do begin inc(n); read(a[n]); end;
readln;
m:=0; while not eoln(input) do begin inc(m); read(b[m]); end;
close(output);
end;
procedure prefix;
var j,k:longint;
begin
pi[1]:=0; k:=0;
for j:=2 to n do begin
while(k>0)and(a[k+1]<>a[j])do k:=pi[k];
if(a[k+1]=a[j])then inc(k);
pi[j]:=k;
end;
end;
procedure KMP;
var i,q:longint;
begin
prefix;
q:=0; nr:=0;
for i:=1 to m do begin
while(q>0)and(a[q+1]<>b[i])do q:=pi[q];
if(a[q+1]=b[i])then inc(q);
if(q=n)then begin
inc(nr);
if(nr<=1000)then s[nr]:=i-n;
q:=pi[q];
end;
end;
end;
procedure scrie;
var i:longint;
begin
assign(output,outfile); rewrite(output);
writeln(nr);
if(nr>1000)then nr:=1000;
for i:=1 to nr do write(s[i],' ');
close(output);
end;
begin
citire; KMP; scrie;
end.