Cod sursa(job #2295439)

Utilizator dianamichesaRosu Diana Michesa dianamichesa Data 3 decembrie 2018 17:41:23
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int N = 10000100;
const int MOD = 15091;
char cuv[25];
char s[N];
vector <int> h[16001];
long long n, rez;
bool exista (int has) {
    int k = has % MOD;
    for(int  i = 0; i < h[k].size(); i ++)
        if(h[k][i] == has)
        return true;
    return false;
}
void citire () {
    f >> s;
    while(f >> cuv) {
        //g << cuv << ' ';
        int p3 = 0;
        n = strlen (cuv);
        for(int  i = 0; i < n; i ++)
            p3 = p3 * 3 + cuv[i] - 'a' + 1;
        h[p3 % MOD].push_back(p3);
        //g << p3 << '\n';
    }
}
int main()
{
    citire ();
    long long p3 = 1;
    for(int  i = 1; i < n; i ++)
        p3 *= 3;
    long long has = 0;
    for(int  i = 0; i < n; i ++) {
        has = has * 3 + s[i] - 'a' + 1;
        //g << s[i];
    }
    if(exista(has))
        rez ++;
    int i = n;
  /*  for(int  i = 1; i <= 50; i ++)
        if(exista(i))
        //g << i << '\n';*/
    while(i < strlen(s)) {
        has -= (s[i - n] - 'a' + 1) * p3;
        has = has * 3 + s[i] - 'a' + 1;
        //g << has << ' ';
        if(exista(has))
            rez ++;
        i ++;
    }
    g << rez;
    //g << s;
    return 0;
}