Cod sursa(job #2223948)

Utilizator giotoPopescu Ioan gioto Data 22 iulie 2018 12:46:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;

char s[10000005];
char c[25];
const int MOD1 = 100003;
const int MOD2 = 100019;
int Sol, Lc;
vector <int> v[MOD2 + 5];
inline bool find(int H1, int H2){
    for(auto it : v[H2])
        if(it == H1) return 1;
    return 0;
}
inline void addHash(int H1, int H2){
    if(!find(H1, H2)) v[H2].push_back(H1);
}

int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    fgets(s, sizeof(s), stdin);

    while(!feof(stdin)){
        fgets(c, sizeof(c), stdin);
        Lc = strlen(c) - 1;
        int H1 = 0, H2 = 0;
        for(int i = 0; i < Lc ; ++i){
            H1 = (H1 * 3 + c[i] - 'a' + 1) % MOD1;
            H2 = (H2 * 3 + c[i] - 'a' + 1) % MOD2;
        }
        addHash(H1, H2);
    }

    int H1 = 0, H2 = 0, p1 = 1, p2 = 1;
    for(int i = 0; i < Lc ; ++i){
        if(i != 0) p1 = (p1 * 3) % MOD1, p2 = (p2 * 3) % MOD2;
        H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
        H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
    }

    Sol += find(H1, H2);
    int L = strlen(s) - 1;
    for(int i = Lc; i < L ; ++i){
        H1 = ((H1 - (s[i - Lc] - 'a' + 1) * p1 + MOD1) % MOD1 * 3 + s[i] - 'a' + 1) % MOD1;
        H2 = ((H2 - (s[i - Lc] - 'a' + 1) * p2 + MOD2) % MOD2 * 3 + s[i] - 'a' + 1) % MOD2;
        Sol += find(H1, H2);
    }

    printf("%d", Sol);
    return 0;
}