Cod sursa(job #1483514)

Utilizator hrazvanHarsan Razvan hrazvan Data 9 septembrie 2015 15:30:41
Problema Abc2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#define MAXT 100000000
#define MAXL 20
#define MAXN 50000
#define MOD 666013
#define BASE 598729
char text[MAXT + 2], cuv[MAXN + 1][MAXL + 2];
int next[MAXN], ult[MOD];

inline char same(int st, int dr, int c){
  int i;
  for(i = st; i <= dr; i++)
    if(text[i] != cuv[c][i - st])
      return 0;
  return 1;
}

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

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, h;
  while(lit(cuv[0][l]))
    l++;
  for(i = 0; i < MOD; i++)
    ult[i] = -1;
  for(i = 0; i < nr; i++){
    h = 0;
    for(j = 0; j < l; j++)
      h = (1LL * h * BASE + cuv[i][j] - 'a' + 1) % MOD;
    next[i] = ult[h];
    ult[h] = i;
  }
  int rez = 0, poz, ptr = 1, ad;
  for(i = 0; i < l; i++)
    ptr = 1LL * ptr * BASE % MOD;
  h = 0;
  for(i = 0; i < l - 1; i++)
    h = (1LL * h * BASE + text[i] - 'a' + 1) % MOD;
  for(i = l - 1; lit(text[i]); i++){
    h = (1LL * h * BASE + text[i] - 'a' + 1) % MOD;
    if(i - l >= 0)
      h -= (text[i - l] - 'a' + 1) * ptr % MOD;
    if(h < 0)
      h += MOD;
    poz = ult[h];
    ad = 0;
    while(poz > -1){
      if(same(i - l + 1, i, poz))
        ad = 1;
      poz = next[poz];
    }
    rez += ad;
  }
  FILE *out = fopen("abc2.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}