Pagini recente » Cod sursa (job #2195070) | Cod sursa (job #3207521) | Cod sursa (job #1543681) | Cod sursa (job #790263) | Cod sursa (job #186115)
Cod sursa(job #186115)
program strmatch;
const fi='strmatch.in';fo='strmatch.out';
var a,b:array[1..1000000]of char;
pi:array[1..1000000]of longint;
s:array[0..1000000]of longint;
n,m:longint;
i:longint;
f,g:text;
procedure creare_prefix;
var q,k:longint;
begin
k:=0;
pi[1]:=0;
for q:=2 to m do begin
while(k>0)and(a[k+1]<>a[q])do k:=pi[k];
if a[k+1]=a[q] then inc(k);
pi[q]:=k;
end;
end;
procedure KMP;
var q,i:longint;
begin
fillchar(pi,sizeof(pi),0);
fillchar(s,sizeof(s),0);
q:=0;
creare_prefix;
for i:=1 to n do begin
while(q>0)and(a[q+1]<>b[i]) do q:=pi[q];
if(a[q+1]=b[i])then q:=q+1;
if q=m then begin
inc(s[0]);
s[s[0]]:=i-m;
q:=pi[q];
end;
end;
end;
begin
assign(f,fi);reset(f);
assign(g,fo);rewrite(g);
i:=0;
while not eoln(f) do begin
inc(i);
read(f,a[i]);
end;
m:=i;
readln(f);
i:=0;
while not eoln(f) do begin
inc(i);
read(f,b[i]);
end;
n:=i;
KMP;
writeln(g,s[0]);
for i:=1 to s[0] do write(g,s[i],' ');
close(f);
close(g);
end.