Cod sursa(job #2297712)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 6 decembrie 2018 12:16:37
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <unordered_map>
#include <cstdio>
#include <cstring>
using namespace std;
const int LMAX = 10000005;
const int NMAX = 50005;
char s[LMAX];
char a[NMAX][25];
unordered_map <unsigned int, bool> mp;
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');
    }
    mp[nr] = 1;
  }
  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;
  if(mp.find(nr) != mp.end()) {
    sol++;
  }
  for(int i = n; i < m; i++) {
    nr = nr - (s[i - n] - 'a') * p3[n - 1];
    nr = nr * 3 + (s[i] - 'a');
    if(mp.find(nr) != mp.end()) {
      sol++;
    }
  }
  printf("%d\n", sol);
  return 0;
}