Cod sursa(job #1483539)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 septembrie 2015 15:54:40
Problema Abc2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <stdio.h>
#define MAXT 100000000
#define MAXL 20
#define MAXN 50000
char text[MAXT + 2], cuv[MAXN + 1][MAXL + 2];
int v[MAXN + 1];

inline char lit(char ch){
  if(ch >= 'a' && ch <= 'z')
    return 1;
  return 0;
}

inline char caut(int x, int n, int k){
  int i = 0, pas = (1 << k);
  while(pas > 0){
    if(i + pas < n && v[i + pas] < x)
      i += pas;
    pas >>= 1;
  }
  if(i != n - 1 && v[i + 1] == x)
    return 1;
  return 0;
}

void qs(int st, int dr){
  int i = st, j = dr, piv = v[(st + dr) / 2], aux;
  while(i <= j){
    while(v[i] < piv)
      i++;
    while(v[j] > piv)
      j--;
    if(i <= j){
      aux = v[i];  v[i] = v[j];  v[j] = aux;
      i++;  j--;
    }
  }
  if(st < j)
    qs(st, j);
  if(i < dr)
    qs(i, dr);
}

int main(){
  FILE *in = fopen("abc2.in", "r");
  fgets(text, MAXT + 2, in);
  int nr = 0;
  char g = 1;
  while(g){
    fgets(cuv[nr], MAXL + 2, in);
    if(!lit(cuv[nr][0]))
      g = 0;
    nr++;
  }
  nr--;
  fclose(in);
  int i, j, l = 0;
  while(lit(cuv[0][l]))
    l++;
  for(i = 0; i < nr; i++)
    for(j = 0; j < l; j++)
      v[i] = v[i] * 3 + cuv[i][j] - 'a';
  qs(0, nr - 1);
  int rez = 0, poz, ptr = 1, ad, h, k, cnr;
  cnr = nr;
  k = 0;
  while(cnr > 0){
    cnr /= 2;
    k++;
  }
  k--;
  for(i = 0; i < l; i++)
    ptr *= 3;
  h = 0;
  for(i = 0; i < l - 1; i++)
    h = h * 3 + text[i] - 'a';
  for(i = l - 1; lit(text[i]); i++){
    h = h * 3 + text[i] - 'a';
    if(i - l >= 0)
      h -= ptr * (text[i - l] - 'a');
    if(caut(h, nr, k))
      rez++;
  }
  FILE *out = fopen("abc2.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}