12 solutions

  • 13
    @ 2021-8-26 15:24:32

    显然,这题也可以考虑字符串哈希。

    将每个字符串看成 pp 进制数,将其对 MM 取模后的结果作为哈希值。

    例如 S=abb,p=10,M=16384S=abb,p=10,M=16384 , hs=122hs=122

    通常 P=13331,131P=13331,131 M=264M=2^{64} 或者较大质数。

    我写的是拉 MMvector 存另一模数的哈希值。

    int main() {
        int n;
        scanf("%d", &n);
        int ans = n;
    
        for (int i = 1; i <= n; ++i) {
            string str;
            cin >> str;
            int len = str.length();
            //cerr<<104<<endl;
            ll hs1 = 0, hs2 = 0;
    
            for (int j = 0; j < len; ++j) {
                hs1 *= p, hs2 *= p;
                hs1 += str[j], hs2 += str[j];
                hs1 %= mod1, hs2 %= mod2;
            }
    
            //cerr<<hs1<<' '<<hs2<<endl;
            int fl = 0;
    
            for (int j = 0; j < h[hs1].size(); ++j) {
                if (h[hs1][j] == hs2) {
                    ans--;
                    fl = 1;
                    break;
                }
            }
    
            if (fl == 0)
                h[hs1].push_back(hs2);
        }
    
        cout << ans << endl;
        return 0;
    }
    

    Information

    ID
    180
    Time
    300~1000ms
    Memory
    1024MiB
    Difficulty
    3
    Tags
    # Submissions
    1871
    Accepted
    261
    Uploaded By