Cod sursa(job #2299033)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 8 decembrie 2018 19:29:27
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int LMAX = 10000005;
const int NMAX = 50005;
const int MOD = 10041;
char s[LMAX];
char a[NMAX][25];
vector <int> vec[MOD];
int p3[25];

int main() {
  freopen("abc2.in", "r", stdin);
  freopen("abc2.out", "w", stdout);
  scanf("%s", s);
  int m = (int)strlen(s);
  int top = 1;
  for( ; scanf("%s", a[top]) != EOF; top++);
  top--;
  int n = (int)strlen(a[1]);
  for(int i = 1; i <= top; i++) {
    unsigned int nr = 0;
    for(int j = 0; j < n; j++) {
      nr = nr * 3 + (a[i][j] - 'a');
    }
    bool ok = 0;
    int mm = nr % MOD;
    for(int it = 0; ok == 0 && it < vec[mm].size(); it++) {
      if(vec[mm][it] == nr) {
        ok = 1;
      }
    }
    if(ok == 0) {
      vec[mm].push_back(nr);
    }
  }
  unsigned int nr3 = 1;
  for(int i = 0; i <= 21; i++) {
    p3[i] = nr3;
    nr3 = nr3 * 3;
  }
  if(m < n) {
    printf("0\n");
    return 0;
  }
  unsigned int nr = 0;
  for(int i = 0; i < n; i++) {
    nr = nr * 3 + (s[i] - 'a');
  }
  unsigned int sol = 0;
  int mm = nr % MOD;
  for(int it = 0; it < vec[mm].size(); it++) {
    if(vec[mm][it] == nr) {
      sol++;
      it = (int)vec[mm].size();
    }
  }
  for(int i = n; i < m; i++) {
    nr = nr - (s[i - n] - 'a') * p3[n - 1];
    nr = nr * 3 + (s[i] - 'a');
    int mm = nr % MOD;
    for(int it = 0; it < vec[mm].size(); it++) {
      if(vec[mm][it] == nr) {
        sol++;
        it = (int)vec[mm].size();
      }
    }
  }
  printf("%d\n", sol);
  return 0;
}