Cod sursa(job #2388559)

Utilizator NeredesinI am not real Neredesin Data 26 martie 2019 10:33:01
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <cstring>
#include <vector>

#define MOD 50003

using namespace std;

ifstream in("abc2.in");
ofstream out("abc2.out");

int nr, i, l;
int n, j;

unsigned int a,q[23];

char w[10000012];
char c[24];

vector <unsigned int> mp[MOD+2];

bool caut(unsigned int jeg) {
  int r = jeg % MOD;
  int z = mp[jeg % MOD].size();

  for(j = 0; j < z; j++)
    if(mp[r][j] == jeg)
      return 1;

  return 0;
}

int main()
{
  in >> (w + 1);

  l = strlen(w + 1);

  q[1] = 1;

  for(i = 2; i <= 20; i++)
    q[i] = q[i - 1] * 3;

  while(in >> (c + 1)) {
    n = strlen(c + 1);

    for(i = 1, a = 0; i <= n; i++)
      a = a + q[i] * (c[i] - 'a');

    mp[a % MOD].push_back(a);
  }

  for(i = 1, a = 0; i <= n; i++)
    a = a + q[i] * (w[i] - 'a');

  nr += caut(a);

  for(i = n + 1; i <= l; i++) {
    a /= 3;
    a = a + q[n] * (w[i] - 'a');
    nr += caut(a);
  }

  out << nr;

  in.close();
  out.close();

  return 0;
}