Cod sursa(job #2297705)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 6 decembrie 2018 12:06:31
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD1 = 1000000007;
const int MOD2 = 1000000009;
const int LMAX = 10000005;
const int NMAX = 50005;
char s[LMAX];
char a[NMAX][25];
map <unsigned int, unsigned int> mp1;
map <unsigned int, unsigned int> mp2;
int p31[25];
int p32[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 nr1 = 0, nr2 = 0;
    for(int j = 0; j < n; j++) {
      nr1 = (nr1 * 3 + (a[i][j] - 'a')) % MOD1;
      nr2 = (nr2 * 3 + (a[i][j] - 'a')) % MOD2;
    }
    mp1[nr1]++;
    mp2[nr2]++;
  }
  unsigned int nr31 = 1, nr32 = 1;
  for(int i = 0; i <= 21; i++) {
    p31[i] = nr31;
    p32[i] = nr32;
    nr31 = (nr31 * 3) % MOD1;
    nr32 = (nr32 * 3) % MOD2;
  }
  if(m < n) {
    printf("0\n");
    return 0;
  }
  unsigned int nr1 = 0, nr2 = 0;
  for(int i = 0; i < n; i++) {
    nr1 = (nr1 * 3 + (s[i] - 'a')) % MOD1;
    nr2 = (nr2 * 3 + (s[i] - 'a')) % MOD2;
  }
  unsigned int sol = 0;
  if(mp1.find(nr1) != mp1.end() && mp2.find(nr2) != mp2.end()) {
    sol++;
  }
  for(int i = n; i < m; i++) {
    nr1 = (nr1 - (s[i - n] - 'a') * p31[n - 1] + MOD1) % MOD1;
    nr2 = (nr2 - (s[i - n] - 'a') * p32[n - 1] + MOD2) % MOD2;
    nr1 = (nr1 * 3 + (s[i] - 'a')) % MOD1;
    nr2 = (nr2 * 3 + (s[i] - 'a')) % MOD2;
    if(mp1.find(nr1) != mp1.end() && mp2.find(nr2) != mp2.end()) {
      sol++;
    }
  }
  printf("%d\n", sol);
  return 0;
}