Cod sursa(job #99226)

Utilizator gurneySachelarie Bogdan gurney Data 11 noiembrie 2007 00:04:31
Problema Abc2 Scor 0
Compilator fpc Status done
Runda Happy Coding 2007 Marime 2.75 kb
program abc2;
  const
    fin='abc2.in';
    fout='abc2.out';
    lmax=25;
    nmax=51000;
    tr:array['a'..'c'] of integer=(0,1,2);
var
  f:text;
  d:array[0..nmax] of int64;
  a:array[0..10000000] of integer;
  cuv:array[0..25] of integer;
  lga,lg,i,n,x,y:longint;
  c,p3,pmax,aux:int64;
  ch:char;
  hash:array[0..200000,0..50] of longint;
  num:longint;

function h(x:int64):int64;
  begin
    h:=x mod 200000;
  end;

procedure hashtable;
  var
    poz:int64;
    i:longint;
  begin
    for i:=1 to n do
      if d[i]<>d[i-1] then
        begin
          poz:=h(d[i]);
          inc(hash[poz,0]);
          hash[poz,hash[poz,0]]:=i;
        end;
  end;

function query2(x:int64):boolean;
  var
    poz:int64;
    found:boolean;
    i:longint;
  begin
    poz:=h(x);
    found:=false;
    for i:=1 to hash[poz,0] do
      if d[hash[poz,i]]=x then
        begin
          found:=true;
          break;
        end;
    query2:=found;
  end;

procedure qsort(st,dr:longint);
  var
    i,j:longint;
    tmp,x:int64;
  begin
    i:=st;j:=dr;
    x:=d[(st+dr)shr 1];
    repeat
      while d[i]<x do
        inc(i);
      while d[j]>x do
        dec(j);
      if i<=j then
        begin
          tmp:=d[i];d[i]:=d[j];d[j]:=tmp;
          inc(i);dec(j);
        end;
    until i>j;
    if j>st then
      qsort(st,j);
    if i<dr then
      qsort(i,dr);
  end;

begin
  assign(f,fin);
    reset(f);
    d[0]:=-1;
    lga:=0;
    while not(eoln(f)) do
      begin
        read(f,ch);
        inc(lga);
        a[lga]:=tr[ch];
      end;
    readln(f);
    n:=1;lg:=0;pmax:=1;
    while not(eoln(f)) do
      begin
        read(f,ch);
        inc(lg);
        cuv[lg]:=tr[ch];
        pmax:=pmax*3;
      end;
    pmax:=pmax div 3;
    p3:=pmax;
    for i:=1 to lg do
      begin
        aux:=cuv[i];
        inc(d[1],p3*aux);
        p3:=p3 div 3;
      end;
    readln(f);
    while not(eof(f)) do
      begin
        inc(n);
        p3:=pmax;
        for i:=1 to lg do
          begin
            read(f,ch);
            aux:=tr[ch];
            inc(d[n],aux*p3);
            p3:=p3 div 3;
          end;
        readln(f);
      end;
  close(f);
  assign(f,fout);
    rewrite(f);
    qsort(1,n);
    c:=0;
    hashtable;
    p3:=pmax;
    for i:=1 to lg do
      begin
        aux:=a[i];
        aux:=aux*p3;
        c:=c+aux;
        p3:=p3 div 3;
      end;
    num:=0;
    for i:=lg+1 to lga do
      begin
        if query2(c) then
          inc(num);
        aux:=a[i-lg];
        aux:=aux*pmax;
        dec(c,aux);
        c:=c*3;
        aux:=a[i];
        inc(c,aux);
      end;
    if query2(c) then
      inc(num);
    writeln(f,num);
  close(f);
end.