Cod sursa(job #166023)

Utilizator gurneySachelarie Bogdan gurney Data 27 martie 2008 12:31:20
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.55 kb
program strmatch;
  const
    fin='strmatch.in';
    fout='strmatch.out';
    nmax=2000000;
  type
    alfa='A'..'z';
    chararray=array[0..nmax] of alfa;
    pchararray=^chararray;

  var
    a,b:pchararray;
    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;
    for i:=1 to n do
      begin
        while (k>0) and (b^[i]<>a^[k+1]) do
          k:=t[k];
        if (b^[i]=a^[k+1]) then
          inc(k);
        if k=m then
          begin
            inc(nr);
            if nr<1001 then
              meci[nr]:=i-m+1;
            k:=t[k];
          end;
      end;
  end;

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