Cod sursa(job #166048)

Utilizator gurneySachelarie Bogdan gurney Data 27 martie 2008 12:54:16
Problema Potrivirea sirurilor Scor 38
Compilator fpc Status done
Runda Arhiva educationala Marime 1.5 kb
program strmatch;
  const
    fin='strmatch.in';
    fout='strmatch.out';
    nmax=2000006;

  type
    alfa='A'..'z';
    chararray=array[0..nmax] of alfa;
    pchararray=^chararray;

  var
    a:pchararray;
    c:char;
    t:array[0..nmax] of longint;
    meci:array[1..1001] of longint;
    i,j,k,n,m,nr:longint;

function min(x,y:longint):longint;
  begin
    if x<y then
      min:=x
    else
      min:=y;
  end;

procedure prefix;
  var
    k,q:longint;
  begin
    t[1]:=0;
    k:=0;
    for q:=2 to m do
      begin
        while (k>0) and (a^[q]<>a^[k+1]) do
          k:=t[k];
        if a^[q]=a^[k+1] then
          inc(k);
        t[q]:=k;
      end;
  end;

procedure kmp;
  var
    k,i:longint;
  begin
    prefix;
    k:=0;
    read(c);
    i:=1;
    while not(seekeoln(input)) do
      begin
        while (k>0) and (c<>a^[k+1]) do
          k:=t[k];
        if (c=a^[k+1]) then
          inc(k);
        if k=m then
          begin
            inc(nr);
            if nr<1001 then
              meci[nr]:=i-m;
            k:=t[k];
          end;
        inc(i);
        read(c);
      end;
  end;

begin
  assign(input,fin);
    reset(input);
    m:=0;
    new(a);
    while not(eoln(input)) do
      begin
        inc(m);
        read(a^[m]);
      end;
    readln;
  assign(output,fout);
    rewrite(output);
    kmp;
    close(input);
    writeln(nr);
    for i:=1 to min(nr,1000) do
      write(meci[i],' ');
  close(output);
end.