Cod sursa(job #186698)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 28 aprilie 2008 17:26:07
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.21 kb
var a,b:array[1..2000001] of char;
    nr,n,m,k,q,i:longint;
    v,vv:array[1..2000001] of longint;
    ok:boolean;
procedure prefix;inline;
  begin
    v[1]:=0; k:=0;
    for q:=2 to m do
       begin
         while(k>0)and(b[k+1]<>b[q]) do k:=v[k];
         if b[k+1]=b[q] then k:=k+1;
         v[q]:=k;
       end;
  end;
procedure kmp; inline;
  begin
    k:=0; nr:=0;
for q:=1 to n do
  begin
    while (k>0)and(a[q]<>b[k+1]) do k:=v[k];
    if a[q]=b[k+1] then k:=k+1;
    if k=m then begin inc(nr); if nr<=1000 then vv[nr]:=q-m; k:=v[k]; end;
  end;
  end;
begin
assign(input,'strmatch.in'); reset(input); assign(output,'strmatch.out'); rewrite(output);
m:=0;
while not seekeoln do begin inc(m); read(b[m]);end;
readln;
n:=0;
while not seekeoln do begin inc(n); read(a[n]);end;
if n=m then
  begin
    ok:=true;
    i:=1;
    while (i<=n)and(ok) do
      begin
        if a[i]<>b[i] then ok:=false;
        inc(i);
      end;
      if ok then begin writeln('1'); writeln(0); end
             else begin writeln('0'); end;
  end
     else
   begin
prefix;
kmp;
writeln(nr);
if nr>1000 then nr:=1000;
for q:=1 to nr do
   write(vv[q],' '); end;
close(input); close(output);
end.