Cod sursa(job #2223935)

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

char s[10000005];
char c[25];
const int MOD1 = 100003;
const int MOD2 = 100019;
int Sol;
vector <pair <int, int> > v[MOD2 + 5];
inline void addHash(int H1, int H2, int pos){
    for(auto &it : v[H2])
        if(it.first == H1){++it.second; return ;}
    v[H2].push_back({H1, 1});
}
inline void find(int H1, int H2){
    vector <pair <int, int> > :: iterator it = v[H2].begin();
    for(it; it != v[H2].end() ; ++it){
        if(it->first == H1){
            Sol += it->second;
            v[H2].erase(it);
            return ;
        }

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

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

    int L = strlen(s) - 1, Lc = strlen(c) - 1;
    if(L < Lc){printf("0"); return 0;}
    int H1 = 0, H2 = 0, p1 = 1, p2 = 1;
    for(int i = 0; i < Lc ; ++i){
        H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
        H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
        p1 = (p1 * 3) % MOD1; p2 = (p2 * 3) % MOD2;
    }
    addHash(H1, H2, 0);
    for(int i = Lc; i < L ; ++i){
        H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
        H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
        H1 = (H1 - p1 * (s[i - Lc] - 'a' + 1));
        H2 = (H2 - p2 * (s[i - Lc] - 'a' + 1));
        if(H1 < 0) H1 += MOD1;
        if(H2 < 0) H2 += MOD1;

        addHash(H1, H2, i - Lc + 1);
    }

    do{
        H1 = 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;
        }
        find(H1, H2);
        fgets(c, sizeof(c), stdin);
    }while(!feof(stdin));

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