Cod sursa(job #1551994)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 16 decembrie 2015 23:26:02
Problema Restante Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

#define MaxN 360000
#define MaxL 20
#define Sigma 27
#define MOD1 1572869
#define MOD2 666013
#define MOD3 98317
#define BASE 131

unsigned short freq[Sigma];
map <pair <int, pair <int, int>>, unsigned short> H;

int main(void) {
    freopen("restante.in", "r", stdin);
    freopen("restante.out", "w", stdout);
    int N, q, t, z, ans;
    char c;

    scanf("%d\n", &N);
    for (int i = 0; i < N; i++) {
        while ((c = getchar_unlocked()) != '\n') {
            freq[c - 'a']++;
        }
        q = 0;
        t = 0;
        z = 0;
        for (int j = 0; j < Sigma; j++) {
            while (freq[j] > 0) {
                q = (q * BASE + j) % MOD1;
                t = (t * BASE + j) % MOD2;
                z = (z * BASE + j) % MOD3;
                freq[j]--;
            }
        }
        H[make_pair(z, make_pair(q, t))]++;
    }
    fseek(stdin, 0, SEEK_SET);
    scanf("%d\n", &N);
    ans = 0;
    for (int i = 0; i < N; i++) {
        while ((c = getchar_unlocked()) != '\n') {
            freq[c - 'a']++;
        }
        q = 0;
        t = 0;
        z = 0;
        for (int j = 0; j < Sigma; j++) {
            while (freq[j] > 0) {
                q = (q * BASE + j) % MOD1;
                t = (t * BASE + j) % MOD2;
                z = (z * BASE + j) % MOD3;
                freq[j]--;
            }
        }
        ans += (H[make_pair(z, make_pair(q, t))] == 1);
    }
    printf("%d\n", ans);
    fclose(stdout);
    return 0;
}