洛谷 P3370 【模板】字符串哈希

// P3370【模板】字符串哈希 —— 正解：双模数字符串哈希，把 N 个串各变成一个「数对」再去重
//
// ★ 题目就一句话：N 个串里有几个不同的。N ≤ 10⁴，每个串约 1000 个字符（最长 1500）。
//   ⇒ 输入最大约 15 MB，「不同的有几个」= 去重。
//
// ★★ 这一章的地基只有一句：**把一个串变成一个数**。
//   变完之后「两个串一不一样」就是「两个数一不一样」—— 而数是能排序、能进 set 的定长的东西。
//
// ⚠ 三处这道题特有的、和本章正文不一样的地方：
//   ① 字符集是**数字 + 大小写字母**（大小写敏感），不是正文里的纯小写；
//      ⇒ 本章 fast.cpp 那句 `c - 'a' + 1` 搬过来会算出负数。**那不要紧**（见 p3370Neg.cpp），
//        但顺手改成 `c - '0'` 就要命（见 p3370Zero.cpp）—— 因为 '0' 会被映射成 **0**。
//      ⇒ 这里干脆用**字符本身的 ASCII 码**：62 个字符全在 48..122，一个都不是 0。
//   ② 这道题问的是「N 个串**两两**比」，不是「一个模式串扫一遍」
//      ⇒ 生日悖论那一笔账（正文第 8 步第三笔）就是这道题：C(10⁴,2) ≈ 5×10⁷ 对。
//        单模数 10⁹+7 的期望碰撞是 0.05 对 —— 看着安全，可**出题人可以照着模数造数据**。
//   ③ 串长最长 **1500** ⇒ 正文那个「长度 1024 的 Thue–Morse 反例」**装得进这道题**。
//
// 复杂度：O(Σ|s| + N log N)。
#include <bits/stdc++.h>
using namespace std;

const long long MOD1 = 1000000007, MOD2 = 998244353;
const long long B1 = 131, B2 = 13331;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> v;
    v.reserve(n);
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        long long a = 0, b = 0;
        for (char c : s) {
            long long x = (unsigned char)c;        // ⚠ 直接用 ASCII 码：48..122，没有 0
            a = (a * B1 + x) % MOD1;
            b = (b * B2 + x) % MOD2;
        }
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end());
    cout << (int)(unique(v.begin(), v.end()) - v.begin()) << '\n';
    return 0;
}

// P3370 —— 把「三条路各要摸多少个字符」和「秒表」量出来，而**两把尺子会打架**。
//
// ★ 这一页真正要回答的问题有两个，而它们的答案方向相反：
//   ① 「两两比」到底差在哪儿 —— 它答案是对的，对拍永远不会说它一句话
//      （[第 20 章 P5019](/sol/p5019/) 那条），只能数次数 + 掐秒表。
//   ② ★★★ **哈希在这道模板题上到底快不快** —— 量完才知道：**它比 set<string> 还慢。**
//
// 三条路，按「要摸多少个字符」排：
//   ① 两两比      C(N,2) **对**，每对最坏 M 个字符
//   ② 排序 / set  N log N **对**，每对最坏 M 个字符
//   ③ 哈希        Σ|s| 个字符（**每个字符都得摸一遍**），之后每次比较都是 O(1)
//
// ⚠⚠ 而 ① ② 的「最坏」都要看**数据形状**：`a == b` 先比长度、再 memcmp，
//   第一个不同的字节就返回 —— 随机串上一对只摸 1 个字符。
//   ⇒ 掐死它们的形状是「**所有串共享一个很长的前缀**」。这就是下面每张表都有两列的原因。
//
// 用法：
//   ./p3370Count cmp      次数表（N = 250/500/1000，M = 200，两种形状）
//   ./p3370Count time     顶格（N = 10⁴、M = 1000）的次数 ＋ 秒表
//   ./p3370Count table    两张一起
//   ./p3370Count csv      只打 `键,值`，给 check:viz 用
#include <bits/stdc++.h>
using namespace std;

// 按显示宽度补空格：ASCII 算 1 格，汉字 / ★ 算 2 格
// ⚠ 含中文的列不能用 printf 的 %-Ns 对齐 —— 那个数的是字节，一个汉字占 3 字节却只显示 2 格。
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

static mt19937 rng(20260909u);
static const char* ALPHA =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

/** shape = 0 随机串；shape = 1 所有串共享长度 m−4 的同一个前缀 */
static vector<string> makeData(int n, int m, int shape) {
    vector<string> a(n);
    string pre;
    if (shape == 1) { pre.resize(m - 4); for (char& c : pre) c = ALPHA[rng() % 62]; }
    for (int i = 0; i < n; i++) {
        string s;
        if (shape == 1) { s = pre; while ((int)s.size() < m) s.push_back(ALPHA[rng() % 62]); }
        else { s.resize(m); for (char& c : s) c = ALPHA[rng() % 62]; }
        a[i] = s;
    }
    return a;
}

static long long cmps = 0;

/** 带计数的串比较：逐字符比，第一个不同就停 —— 和 std::string 的 == / < 是同一个行为 */
static int cmpCount(const string& x, const string& y) {
    size_t i = 0, n = min(x.size(), y.size());
    while (i < n) { cmps++; if (x[i] != y[i]) return x[i] < y[i] ? -1 : 1; i++; }
    if (x.size() == y.size()) return 0;
    return x.size() < y.size() ? -1 : 1;
}

static long long pairChars(const vector<string>& a) {
    cmps = 0;
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < i; j++) if (cmpCount(a[i], a[j]) == 0) break;
    return cmps;
}

static long long sortChars(vector<string> a) {
    cmps = 0;
    sort(a.begin(), a.end(), [](const string& x, const string& y) { return cmpCount(x, y) < 0; });
    a.erase(unique(a.begin(), a.end(),
                   [](const string& x, const string& y) { return cmpCount(x, y) == 0; }), a.end());
    return cmps;
}

static long long hashChars(const vector<string>& a) {
    long long t = 0;
    for (const string& s : a) t += (long long)s.size();
    return t;                                   // 每个字符摸一次，之后全是 O(1) 的数比较
}

/** 同上，但补在左边（数字列的表头要右对齐才和 %Nlld 对得上） */
static string padLeft(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return string(max(0, width - disp), ' ') + s;
}

/* ---------- 三条路的「真程序」，给秒表用 ---------- */
static const long long MOD1 = 1000000007, MOD2 = 998244353, B1 = 131, B2 = 13331;

static int byHash(const vector<string>& a) {
    vector<pair<long long, long long>> v;
    v.reserve(a.size());
    for (const string& s : a) {
        long long x = 0, y = 0;
        for (char c : s) { x = (x * B1 + (unsigned char)c) % MOD1; y = (y * B2 + (unsigned char)c) % MOD2; }
        v.push_back(make_pair(x, y));
    }
    sort(v.begin(), v.end());
    return (int)(unique(v.begin(), v.end()) - v.begin());
}
static int bySet(const vector<string>& a) { set<string> st(a.begin(), a.end()); return (int)st.size(); }
static int byPair(const vector<string>& a) {
    int ans = 0;
    for (size_t i = 0; i < a.size(); i++) {
        bool seen = false;
        for (size_t j = 0; j < i; j++) if (a[i] == a[j]) { seen = true; break; }
        if (!seen) ans++;
    }
    return ans;
}

#define TIMEIT(expr, out) do { \
    auto _t0 = chrono::steady_clock::now(); \
    volatile int _r = (expr); (void)_r; \
    (out) = chrono::duration<double, milli>(chrono::steady_clock::now() - _t0).count(); \
} while (0)

/** 跑三次取中位数 —— 亚秒级的秒表单次量会被并行的闸门晃翻（[第 45 章那一跤](/sol/p1923/)） */
#define TIMEIT3(expr, out) do { \
    double _v[3]; \
    for (int _k = 0; _k < 3; _k++) TIMEIT(expr, _v[_k]); \
    sort(_v, _v + 3); (out) = _v[1]; \
} while (0)

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    bool csv = (mode == "csv");

    /* ---------- ① 小规模次数表：看 N² 的签名 ---------- */
    const int NS[3] = { 250, 500, 1000 };
    long long tab[2][3][3];                      // [shape][n][path]
    for (int shape = 0; shape < 2; shape++)
        for (int k = 0; k < 3; k++) {
            vector<string> a = makeData(NS[k], 200, shape);
            tab[shape][k][0] = pairChars(a);
            tab[shape][k][1] = sortChars(a);
            tab[shape][k][2] = hashChars(a);
        }

    if (mode == "cmp" || mode == "table") {
        printf("★ 每条路要摸多少个字符（M = 200，两种形状）\n\n");
        for (int shape = 0; shape < 2; shape++) {
            printf("%s\n", shape == 0 ? "  随机串（每对第一个字符就分开）"
                                      : "  ★ 共享 196 个字符的前缀（每对都要比到底）");
            printf("    %-6s %s %s %s\n", "N", padLeft("两两比", 14).c_str(), padLeft("排序/set", 14).c_str(), padLeft("哈希", 12).c_str());
            for (int k = 0; k < 3; k++)
                printf("    %-6d %14lld %14lld %12lld\n", NS[k],
                       tab[shape][k][0], tab[shape][k][1], tab[shape][k][2]);
            printf("    N 每翻一倍，「两两比」这一列 ×%.2f、×%.2f  ⇐ O(N²) 的签名\n\n",
                   (double)tab[shape][1][0] / (double)tab[shape][0][0],
                   (double)tab[shape][2][0] / (double)tab[shape][1][0]);
        }
    }

    /* ---------- ② 顶格：次数 ＋ 秒表 ---------- */
    const int BIGN = 10000, BIGM = 1000;
    long long hashTouch = (long long)BIGN * BIGM;
    long long sortTouchR = 0, sortTouchP = 0, pairTouchR = 0;
    long long pairTouchP = (long long)BIGN * (BIGN - 1) / 2 * (BIGM - 3);   // 共前缀：每对都比到第 997 位
    double tHashR = 0, tSetR = 0, tPairR = 0, tHashP = 0, tSetP = 0, tPairP = 0;
    {
        vector<string> big = makeData(BIGN, BIGM, 0);
        sortTouchR = sortChars(big);
        pairTouchR = pairChars(big);
        TIMEIT3(byHash(big), tHashR);
        TIMEIT3(bySet(big), tSetR);
        TIMEIT3(byPair(big), tPairR);
    }
    {
        vector<string> big = makeData(BIGN, BIGM, 1);
        sortTouchP = sortChars(big);
        TIMEIT3(byHash(big), tHashP);
        TIMEIT3(bySet(big), tSetP);
        TIMEIT(byPair(big), tPairP);             // ⚠ 这一格约一秒，只量一次
    }

    if (mode == "time" || mode == "table") {
        printf("★ 顶格 N = 10⁴、每串 1000 个字符：要摸多少个字符\n\n");
        printf("    %s %s %s\n", padDisp("", 22).c_str(), padLeft("随机串", 18).c_str(), padLeft("共长前缀", 18).c_str());
        printf("    %s %18lld %18lld\n", padDisp("★ 哈希（双模数）", 22).c_str(), hashTouch, hashTouch);
        printf("    %s %18lld %18lld\n", padDisp("★ set<string>", 22).c_str(), sortTouchR, sortTouchP);
        printf("    %s %18lld %18lld\n", padDisp("✗ 两两比", 22).c_str(), pairTouchR, pairTouchP);
        printf("\n★ 秒表（同一批数据，跑 3 次取中位数；共前缀的两两比只跑 1 次）\n\n");
        printf("    %s %s %s\n", padDisp("", 22).c_str(), padLeft("随机串", 13).c_str(), padLeft("共长前缀", 16).c_str());
        printf("    %s %10.1f ms %10.1f ms\n", padDisp("★ 哈希（双模数）", 22).c_str(), tHashR, tHashP);
        printf("    %s %10.1f ms %10.1f ms\n", padDisp("★ set<string>", 22).c_str(), tSetR, tSetP);
        printf("    %s %10.1f ms %10.1f ms\n", padDisp("✗ 两两比", 22).c_str(), tPairR, tPairP);
        printf("\n    ⚠⚠ 两把尺子打架：按「摸了多少字符」哈希赢 set %.1f 倍，"
               "按秒表 set 赢哈希 %.1f 倍（共前缀那一列）\n",
               (double)sortTouchP / (double)hashTouch, tHashP / tSetP);
    }

    if (csv) {
        for (int shape = 0; shape < 2; shape++)
            for (int k = 0; k < 3; k++)
                printf("cmp%d_%d,%lld %lld %lld\n", shape, NS[k],
                       tab[shape][k][0], tab[shape][k][1], tab[shape][k][2]);
        printf("grow0,%.2f %.2f\n", (double)tab[0][1][0] / (double)tab[0][0][0],
               (double)tab[0][2][0] / (double)tab[0][1][0]);
        printf("grow1,%.2f %.2f\n", (double)tab[1][1][0] / (double)tab[1][0][0],
               (double)tab[1][2][0] / (double)tab[1][1][0]);
        printf("hashTouch,%lld\nsortTouchR,%lld\nsortTouchP,%lld\npairTouchR,%lld\npairTouchP,%lld\n",
               hashTouch, sortTouchR, sortTouchP, pairTouchR, pairTouchP);
        printf("tHashR,%.1f\ntSetR,%.1f\ntPairR,%.1f\n", tHashR, tSetR, tPairR);
        printf("tHashP,%.1f\ntSetP,%.1f\ntPairP,%.1f\n", tHashP, tSetP, tPairP);
        printf("ratioTouch,%.1f\nratioTime,%.1f\n",
               (double)sortTouchP / (double)hashTouch, tHashP / tSetP);
    }
    return 0;
}

// P3370 —— 四种读法读同一份顶格输入，各自报「读进来花了多少毫秒」。
//   ./p3370Read sync   <文件>   默认的 cin >> string（什么都不关）
//   ./p3370Read nosync <文件>   ios::sync_with_stdio(false)
//   ./p3370Read scanf  <文件>   scanf("%s")
//   ./p3370Read fread  <文件>   一次 fread 吞进来，自己按空白切
//
// ★ 为什么这道题非量一遍不可：题面的 100% 档是 `N ≤ 10⁴`、`M_i ≈ 1000`、`M_max ≤ 1500`
//   ⇒ 输入是 **10 MB 量级**，而时限只有 1 秒。
//   [第 6 章 P2367](/sol/p2367/) / [第 38 章 P1972](/sol/p1972/) 立过的规矩：
//   **四种读法的倍数跨题几乎不变，变的是绝对时间，而分数线在绝对时间上。**
//
// ⚠⚠ 第二个参数不是可有可无的（[第 47 章 P1308](/sol/p1308/) 那一跤）：
//   给了文件就 `freopen` 到 stdin 上 —— **评测机做的正是这件事**。
//   不给文件读的是**管道**，那时喂数据的那一头会被一起量进来。
//
// ⚠ 输出里带上「读到了几个串、总共多少字节」：四种读法必须给出同一个答案，
//   否则量到的是「读丢了一截」而不是「读得快」（[第 12 章 P1923](/sol/p1923/) 那个桶）。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "sync";
    if (argc > 2 && !freopen(argv[2], "r", stdin)) { fprintf(stderr, "open failed\n"); return 1; }

    long long cnt = 0, bytes = 0;
    auto t0 = chrono::steady_clock::now();
    if (mode == "fread") {
        vector<char> buf;
        {
            const size_t CH = 1 << 20;
            size_t used = 0, got;
            do { buf.resize(used + CH); got = fread(buf.data() + used, 1, CH, stdin); used += got; } while (got == CH);
            buf.resize(used);
        }
        size_t i = 0, n = buf.size();
        while (i < n && !isspace((unsigned char)buf[i])) i++;      // 跳过第一行那个 N
        while (i < n) {
            while (i < n && isspace((unsigned char)buf[i])) i++;
            size_t j = i;
            while (j < n && !isspace((unsigned char)buf[j])) j++;
            if (j > i) { cnt++; bytes += (long long)(j - i); }
            i = j;
        }
    } else if (mode == "scanf") {
        static char tmp[4096];
        int n = 0;
        if (scanf("%d", &n) != 1) n = 0;
        while (scanf("%4000s", tmp) == 1) { cnt++; bytes += (long long)strlen(tmp); }
    } else {
        if (mode == "nosync") { ios::sync_with_stdio(false); cin.tie(nullptr); }
        int n = 0;
        cin >> n;
        string s;
        while (cin >> s) { cnt++; bytes += (long long)s.size(); }
    }
    double ms = chrono::duration<double, milli>(chrono::steady_clock::now() - t0).count();
    printf("%s,%.1f,%lld,%lld\n", mode.c_str(), ms, cnt, bytes);
    return 0;
}

// P3370 数据生成器（对拍用）。用法：./p3370Gen <seed> [档位]，不给档位就是**最终档 5**。
//
// ★ 老规矩：先写清楚「每个错法靠什么才现形」，再决定拧哪个旋钮 —— 这一页四个错法要的东西完全不同：
//
//   ①单模数        ← ★★ 随机数据**结构性**抓不到（C(N,2)/10⁹ 的期望，N 小的时候是 10⁻⁶ 量级）。
//                     只能埋 collide.cpp 造出来的那一对："rnjpnw" / "vwxtxa"。
//   ②自然溢出      ← ★★ 同样只能埋反例：Thue–Morse 长度 **1024** 的 A / B。
//                     ⚠ 而这道题的 M_max = 1500，**装得下**。
//   ③映射到 0      ← 要**两个长度不同的全 '0' 串**（"0" / "00" / "000"）。随机造不出来。
//   ④两两比        ← 答案永远对，对拍看不见 ⇒ 这一页靠 p3370Count.cpp 数次数。
//
//   ★ 外加一份试金石 p3370All（恒输出 N）：顺手写的随机串本来就互不相同
//     ⇒ 连「什么都不做」都是对的。**先让这一档打假它，再谈别的。**
//
// 档位：
//   0  顺手写法：N = 30~60，长度 5~15，62 个字符里随便抽 —— ★ 全不同，试金石在这儿是满分
//   1  ★ 从一个只有 N/2 个原型的池子里抽 —— 真的造出重复
//   2  ★ 档 1 ＋ 埋那一对单模碰撞串
//   3  ★ 档 1 ＋ 埋 Thue–Morse 1024 那一对
//   4  ★ 档 1 ＋ 埋 "0" / "00" / "000"
//   5  ★★ 最终档 = 1 ＋ 2 ＋ 3 ＋ 4 全埋
#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

static const char* ALPHA =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";   // 62 个

static string randStr(int lo, int hi) {
    int len = ri(lo, hi);
    string s(len, ' ');
    for (int i = 0; i < len; i++) s[i] = ALPHA[ri(0, 61)];
    return s;
}

/** Thue–Morse 的前 len 位：t[i] = popcount(i) & 1；flip 把每一位取反 */
static string thueMorse(int len, bool flip) {
    string s(len, 'a');
    for (int i = 0; i < len; i++) {
        int bit = __builtin_popcount((unsigned)i) & 1;
        s[i] = (char)('a' + (bit ^ (flip ? 1 : 0)));
    }
    return s;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int level = argc > 2 ? atoi(argv[2]) : 5;
    rng.seed(seed * 2654435761u + 12345u);

    vector<string> out;
    int n = ri(30, 60);

    if (level == 0) {
        for (int i = 0; i < n; i++) out.push_back(randStr(5, 15));
    } else {
        int pool = max(3, n / 2);
        vector<string> proto;
        for (int i = 0; i < pool; i++) proto.push_back(randStr(5, 15));
        for (int i = 0; i < n; i++) out.push_back(proto[ri(0, pool - 1)]);
        if (level == 2 || level == 5) {                     // ★ 单模碰撞的那一对
            out.push_back("rnjpnw");
            out.push_back("vwxtxa");
        }
        if (level == 3 || level == 5) {                     // ★ 自然溢出的那一对
            out.push_back(thueMorse(1024, false));
            out.push_back(thueMorse(1024, true));
        }
        if (level == 4 || level == 5) {                     // ★ 全 '0' 串
            out.push_back("0");
            out.push_back("00");
            out.push_back("000");
        }
    }

    shuffle(out.begin(), out.end(), rng);
    printf("%d\n", (int)out.size());
    for (const string& s : out) printf("%s\n", s.c_str());
    return 0;
}