字符串哈希：把子串变成一个数，以及它会在哪儿撞

// 标准答案：一个哈希都不用，全靠逐字符比 —— O(nm + q × |t|)
//
// 它是这道题最直白的翻译，也是对拍的标准答案：
//   · 第一问：文本串每个位置都对一遍（和第 48 章 brute.cpp 同一份思路）；
//   · 第二问：两个子串先比长度，再一个字符一个字符比过去。
//
// ★ 它和正解**没有任何共同的想法** —— 正解那边一次字符比较都不做，只比两个整数。
//   于是它们能互相对拍：一边错了，另一边不会跟着错。
//
// ⚠ 而这一章的暴力是真的慢，慢在第二问：q 个询问、每个子串 10⁶ 长，就是 10¹¹ 次字符比较。
//   （第一问反倒不一定慢 —— 第 48 章第 3 步已经量过了。）

#include <bits/stdc++.h>
using namespace std;

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

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();

    vector<int> pos;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && t[i + j] == p[j]) j++;
        if (j == m) pos.push_back(i);
    }
    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';

    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        bool same = (r1 - l1 == r2 - l2);
        for (int d = 0; same && d <= r1 - l1; d++) same = (t[l1 + d] == t[l2 + d]);
        cout << (same ? "Y" : "N") << '\n';
    }
    return 0;
}

// 正解：字符串哈希（双模数），O(n + m + q)
//
// ★ 关键的一步只有一句话：**把子串变成一个数**。
//   把串看成一个 base 进制的数：h(s) = s[0]·b^(k-1) + s[1]·b^(k-2) + … + s[k-1]
//   再对它取模。于是「两个子串相不相等」就变成「两个数相不相等」—— O(1)。
//
// ⚠ 而「一个子串的哈希」能 O(1) 取出来，靠的是**前缀哈希**，
//   它和第 6 章的前缀和是同一个形状（那里是减一下，这里也是减一下，只多乘一个 b 的幂）：
//       h[i] = 前 i 个字符的哈希
//       sub(l, r) = h[r+1] − h[l]·b^(r−l+1)
//
// ⚠⚠ 这一章真正的主课不在这几行，而在「**它会错**」：
//   · 单模数会被生日攻击撞（本章 collide.cpp 三万多个串就撞出一对）；
//   · 自然溢出（unsigned long long）会被 Thue–Morse 序列**对任何奇数 base** 卡死（thue.cpp）。
//   ⇒ 所以这里用**两个模数**：要错就得同时在两个模数上撞，概率约 1 / 10¹⁸。
//
// ⚠ 还有一处很容易写错、而且随机数据抓不到：字符要映射成 **1..26 而不是 0..25**。
//   映射成 0 的话 "a" 和 "aa" 的哈希都是 0 —— 见 wrongBase.cpp。

#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);

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();

    /* ① 前缀哈希 + base 的幂（两套，两个模数各一套） */
    vector<long long> h1(n + 1, 0), h2(n + 1, 0), pw1(n + 1, 1), pw2(n + 1, 1);
    for (int i = 0; i < n; i++) {
        long long c = t[i] - 'a' + 1;             // ⚠ +1：不许有字符映射成 0
        h1[i + 1] = (h1[i] * B1 + c) % MOD1;
        h2[i + 1] = (h2[i] * B2 + c) % MOD2;
        pw1[i + 1] = pw1[i] * B1 % MOD1;
        pw2[i + 1] = pw2[i] * B2 % MOD2;
    }

    /* ② 取子串 t[l..r] 的哈希 —— 就是前缀和那一减 */
    auto sub = [&](int l, int r) {
        int len = r - l + 1;
        long long a = ((h1[r + 1] - h1[l] * pw1[len]) % MOD1 + MOD1) % MOD1;   // ⚠ +MOD 再取模
        long long b = ((h2[r + 1] - h2[l] * pw2[len]) % MOD2 + MOD2) % MOD2;
        return make_pair(a, b);
    };

    /* ③ 第一问：模式串出现在哪些位置（允许重叠） */
    long long g1 = 0, g2 = 0;
    for (char c : p) {
        g1 = (g1 * B1 + (c - 'a' + 1)) % MOD1;
        g2 = (g2 * B2 + (c - 'a' + 1)) % MOD2;
    }
    vector<int> pos;
    for (int i = 0; i + m <= n; i++) {
        pair<long long, long long> s = sub(i, i + m - 1);
        if (s.first == g1 && s.second == g2) pos.push_back(i);
    }
    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';

    /* ④ 第二问：q 个询问，问 t 的两个子串相不相等 —— ★ KMP 做不了这件事，哈希 O(1) 就答 */
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (sub(l1, r1) == sub(l2, r2) ? "Y" : "N") << '\n';
    }
    return 0;
}

// ★★ 把「单模数哈希会撞」量出来，以及把那一对撞上的串**真的造出来**
//
// 这一章正文第 9 步要回答两个不一样的问题，它们的答案差着好几个数量级：
//
//   ① 「我这道题会不会因为哈希撞了而 WA？」
//       —— 匹配一遍是 n 次比较，每次撞的概率 1/M ⇒ 大约 n/M。10⁶ 个位置、M = 10⁹ ⇒ 0.1%。
//   ② 「我把 N 个子串两两比呢？」（去重、放进 map、判有没有重复子串……）
//       —— 那是 C(N,2) 对，期望撞 C(N,2)/M 次。N = 10⁵、M = 10⁹ ⇒ 期望 5 次，**几乎必撞**。
//   ⇒ 这就是生日悖论：同一个模数，问法一换，安全边际差一万倍。
//
// ★ 而 ② 的「期望 5 次」不是印公式，是这份程序数出来的（第一档就在数它）。
//
// 用法（不给参数就是 all —— 三张表一起打）：
//   ./collide all                三件事一起做，排好版
//   ./collide count [N] [seed]   造 N 个互不相同的 6 字母随机串，数单模 / 双模各撞了几对
//   ./collide sweep              种子 1..16 各来一遍，看「期望 5 对」到底像不像话
//   ./collide find  [seed]       一个个造下去，直到撞出第一对 —— 打印用了多少个串、那两个串是什么
//   ./collide csv   [seed]       三件事一起做，只打 `键,值`，给 check:viz 用
//
// ⚠ 攻击的目标是 base = 131、模 = 10⁹+7 —— 和 wrongSingle.cpp 用的**完全一样**。
//   找到的那一对会被写进 gen.cpp 的「碰撞档」，于是对拍能真的打假单模哈希。

#include <bits/stdc++.h>
using namespace std;

const long long MOD1 = 1000000007, MOD2 = 998244353;
const long long B1 = 131, B2 = 13331;
const int LEN = 6;                                  // 串长：26^6 ≈ 3.09×10^8 种，够撞了

// 按显示宽度补空格（含中文的列不能用 %-Ns，那个数的是字节）
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 long long h(const string& s, long long base, long long mod) {
    long long x = 0;
    for (char c : s) x = (x * base + (c - 'a' + 1)) % mod;
    return x;
}

int main(int argc, char** argv) {
    string cmd = (argc > 1) ? argv[1] : "all";
    bool csv = (cmd == "csv");
    bool all = (cmd == "all");
    int N = (argc > 2 && !csv) ? atoi(argv[2]) : 100000;
    unsigned seed = (unsigned)((argc > (csv ? 2 : 3)) ? atoi(argv[csv ? 2 : 3]) : 1);
    mt19937 rng(seed);
    auto make = [&]() {
        string s(LEN, 'a');
        for (int i = 0; i < LEN; i++) s[i] = (char)('a' + rng() % 26);
        return s;
    };

    if (cmd == "count" || all || csv) {
        /* ① 造 N 个互不相同的串（先去重，免得把「同一个串」当成碰撞） */
        unordered_set<string> seen;
        vector<string> all;
        all.reserve(N);
        while ((int)all.size() < N) {
            string s = make();
            if (seen.insert(s).second) all.push_back(s);
        }
        /* ② 数碰撞：单模数、双模数各一遍（排序之后看相邻的是不是一样） */
        vector<long long> one(N), two(N);
        for (int i = 0; i < N; i++) {
            one[i] = h(all[i], B1, MOD1);
            two[i] = h(all[i], B2, MOD2);
        }
        vector<int> idx(N);
        for (int i = 0; i < N; i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            if (one[a] != one[b]) return one[a] < one[b];
            return two[a] < two[b];
        });
        long long c1 = 0, c2 = 0;
        for (int i = 1; i < N; i++) {
            if (one[idx[i]] == one[idx[i - 1]]) {
                c1++;
                if (two[idx[i]] == two[idx[i - 1]]) c2++;
            }
        }
        double exp1 = (double)N * (N - 1) / 2.0 / (double)MOD1;
        double exp2 = (double)N * (N - 1) / 2.0 / ((double)MOD1 * (double)MOD2);
        if (csv) {
            printf("n,%d\nsingle,%lld\ndouble,%lld\n", N, c1, c2);
        } else {
            printf("%d 个互不相同的 %d 字母串，两两比一遍 —— 一共 %lld 对：\n\n",
                   N, LEN, (long long)N * (N - 1) / 2);
            cout << "  " << padDisp("模数", 26) << padDisp("期望撞几对", 14) << "实测撞了\n";
            cout << "  " << padDisp(string(24, '-'), 26) << padDisp(string(12, '-'), 14) << "--------\n";
            char buf[64];
            snprintf(buf, sizeof(buf), "%.2f", exp1);
            cout << "  " << padDisp("单模数 10^9+7", 26) << padDisp(buf, 14) << c1 << "\n";
            snprintf(buf, sizeof(buf), "%.0e", exp2);
            cout << "  " << padDisp("双模数（乘起来约 10^18）", 26) << padDisp(buf, 14) << c2 << "\n";
            printf("\n  => 一个模数挡不住「两两比」：10^9 看着大，开根号才 3 万多。\n");
        }
    }

    if (cmd == "sweep" || all || csv) {
        /* ★ 一个种子不算数：把 16 个种子各跑一遍，看「期望 5 对」到底像不像话 */
        vector<int> got;
        long long sum = 0;
        for (unsigned sd = 1; sd <= 16; sd++) {
            mt19937 r2(sd);
            unordered_set<string> seen2;
            vector<long long> one2;
            one2.reserve(100000);
            while ((int)one2.size() < 100000) {
                string x(LEN, 'a');
                for (int i = 0; i < LEN; i++) x[i] = (char)('a' + r2() % 26);
                if (seen2.insert(x).second) one2.push_back(h(x, B1, MOD1));
            }
            sort(one2.begin(), one2.end());
            int c = 0;
            for (size_t i = 1; i < one2.size(); i++) if (one2[i] == one2[i - 1]) c++;
            got.push_back(c);
            sum += c;
        }
        if (csv) {
            printf("sweep,");
            for (size_t i = 0; i < got.size(); i++) printf("%s%d", i ? " " : "", got[i]);
            printf("\nsweepsum,%lld\n", sum);
        } else {
            printf("\n种子 1..16 各造 10 万个串（单模数 10^9+7，期望每次撞 5.00 对）：\n\n  ");
            for (size_t i = 0; i < got.size(); i++) printf("%d ", got[i]);
            printf("\n\n  => 平均 %.2f 对。单看一个种子，0 到 9 都可能 —— 但「撞不撞」这件事本身，没有悬念。\n",
                   (double)sum / 16.0);
        }
    }

    if (cmd == "find" || all || csv) {
        rng.seed(seed);            // ⚠ 重新播种：csv 档把两件事一起做，不重播的话
                                   //   「造到第几个串撞上」会跟着上一档的随机数走，两边对不上
        /* ★ 生日攻击：一个个造下去，直到有两个不同的串撞上同一个单模哈希 */
        unordered_map<long long, string> box;
        string a, b;
        long long tried = 0;
        while (true) {
            string s = make();
            tried++;
            long long key = h(s, B1, MOD1);
            auto it = box.find(key);
            if (it != box.end() && it->second != s) { a = it->second; b = s; break; }
            box.emplace(key, s);
        }
        long long ha = h(a, B1, MOD1);
        if (csv) {
            printf("tried,%lld\npair,%s %s\nha,%lld\nhb,%lld\nsame2,%d\n",
                   tried, a.c_str(), b.c_str(), ha, h(b, B1, MOD1),
                   h(a, B2, MOD2) == h(b, B2, MOD2) ? 1 : 0);
        } else {
            printf("\n生日攻击（base = 131，模 10^9+7）：造到第 %lld 个串就撞上了。\n\n", tried);
            printf("  \"%s\" 和 \"%s\"  —— 两个串完全不同\n", a.c_str(), b.c_str());
            printf("  它们的单模哈希都是 %lld\n", ha);
            printf("  而第二个模数下：%lld  vs  %lld  => %s\n",
                   h(a, B2, MOD2), h(b, B2, MOD2),
                   h(a, B2, MOD2) == h(b, B2, MOD2) ? "也撞了" : "分开了，双模数挡住了");
            printf("\n  => 找它花了不到一秒。出题人想卡你的单模哈希，成本就是这么低。\n");
        }
    }
    return 0;
}

// ★★ 把「自然溢出哈希」当场打假：Thue–Morse 序列
//
// 很多人图省事，把哈希的模数省掉，直接用 unsigned long long 让它自然溢出
// （相当于模 2⁶⁴）。这看着比取模还安全 —— 2⁶⁴ 那么大，怎么可能撞上？
//
// ★ 可它对**任何奇数 base** 都有一组固定的反例，而且不用碰运气去撞，是**算出来的**：
//
//   Thue–Morse 序列 t[i] = i 的二进制里 1 的个数的奇偶性（0,1,1,0,1,0,0,1,…）。
//   取它前 2^k 位当串 A（0→'a'、1→'b'），把每一位取反得到串 B。
//   ⇒ A 和 B 的哈希之差 = (b^0 ± …) 展开之后正好等于
//         ± Π(j = 0..k−1) (1 − b^(2^j))
//     而 base 是奇数时，(1 − b^(2^j)) 里 2 的因子至少有 j+2 个（j ≥ 1），
//     全乘起来 2 的因子有 1 + Σ(j+2) ≥ 64 个 —— k = 10 时正好够。
//   ⇒ **长度 1024 的那一对，模 2⁶⁴ 必然相等，和 base 取多少无关。**
//
// 用法：
//   ./thue gen <k>     打印两个串（A 和 B），长度 2^k —— 拿去喂给任何自然溢出的哈希
//   ./thue table       k = 8..11 × 五个 base 的实测表（自然溢出 vs 取模 10⁹+7）
//   ./thue csv         同一张表，只打 `键,值`，给 check:viz 用

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

// 按显示宽度补空格：ASCII 算 1 格，非 ASCII（汉字、★）算 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;               // UTF-8 续字节，不算宽度
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

/** Thue–Morse 的前 len 位：t[i] = popcount(i) & 1 */
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;
}

static ull hashNatural(const string& s, ull base) {
    ull h = 0;
    for (char c : s) h = h * base + (ull)(c - 'a' + 1);   // 不取模 —— 让它自然溢出
    return h;
}

static long long hashMod(const string& s, long long base, long long mod) {
    long long h = 0;
    for (char c : s) h = (h * base + (c - 'a' + 1)) % mod;
    return h;
}

int main(int argc, char** argv) {
    string cmd = (argc > 1) ? argv[1] : "table";
    const long long MOD = 1000000007;
    const ull BASES[5] = {131, 13331, 233, 1000003, 20220617};

    if (cmd == "gen") {
        int k = (argc > 2) ? atoi(argv[2]) : 10;
        if (k < 0) k = 0;
        if (k > 20) k = 20;
        int len = 1 << k;
        printf("%s\n%s\n", thueMorse(len, false).c_str(), thueMorse(len, true).c_str());
        return 0;
    }

    bool csv = (cmd == "csv");
    const int LENS[4] = {256, 512, 1024, 2048};
    if (!csv) {
        printf("Thue-Morse 的前 len 位（串 A）和它逐位取反（串 B）—— 这两个串一个字符都不一样。\n");
        printf("下面看它们的哈希撞不撞：\n\n");
        cout << "  " << padDisp("base", 12) << padDisp("自然溢出（模 2^64）", 36) << "模 10^9+7\n";
        cout << "  " << padDisp("", 12);
        for (int i = 0; i < 4; i++) cout << padDisp("len=" + to_string(LENS[i]), 9);
        cout << "len=1024\n";
        cout << "  " << padDisp(string(10, '-'), 12) << padDisp(string(34, 45), 36) << "--------\n";
    }
    for (int b = 0; b < 5; b++) {
        if (!csv) cout << "  " << padDisp(to_string(BASES[b]), 12);
        for (int i = 0; i < 4; i++) {
            int len = LENS[i];
            bool same = hashNatural(thueMorse(len, false), BASES[b])
                     == hashNatural(thueMorse(len, true), BASES[b]);
            if (csv) printf("nat%d_%llu,%d\n", len, BASES[b], same ? 1 : 0);
            else cout << padDisp(same ? "撞上了" : "没撞", 9);
        }
        bool sameMod = hashMod(thueMorse(1024, false), (long long)BASES[b], MOD)
                    == hashMod(thueMorse(1024, true), (long long)BASES[b], MOD);
        if (csv) printf("mod1024_%llu,%d\n", BASES[b], sameMod ? 1 : 0);
        else cout << (sameMod ? "撞上了" : "没撞") << "\n";
    }
    if (!csv) {
        printf("\n  => len = 1024 那两列，五个 base 全部撞上 —— 这不是运气，是算出来的。\n");
        printf("  => 512 还撞不上：2 的因子只攒到 53 个，离 64 还差 11 个。\n");
        printf("  => 而同样这些串，取模 10^9+7 的哈希一次都没撞。\n");
    }
    return 0;
}

// 正解：字符串哈希（双模数），O(n + m + q)
//
// ★ 关键的一步只有一句话：**把子串变成一个数**。
//   把串看成一个 base 进制的数：h(s) = s[0]·b^(k-1) + s[1]·b^(k-2) + … + s[k-1]
//   再对它取模。于是「两个子串相不相等」就变成「两个数相不相等」—— O(1)。
//
// ⚠ 而「一个子串的哈希」能 O(1) 取出来，靠的是**前缀哈希**，
//   它和第 6 章的前缀和是同一个形状（那里是减一下，这里也是减一下，只多乘一个 b 的幂）：
//       h[i] = 前 i 个字符的哈希
//       sub(l, r) = h[r+1] − h[l]·b^(r−l+1)
//
// ⚠⚠ 这一章真正的主课不在这几行，而在「**它会错**」：
//   · 单模数会被生日攻击撞（本章 collide.cpp 三万多个串就撞出一对）；
//   · 自然溢出（unsigned long long）会被 Thue–Morse 序列**对任何奇数 base** 卡死（thue.cpp）。
//   ⇒ 所以这里用**两个模数**：要错就得同时在两个模数上撞，概率约 1 / 10¹⁸。
//
// ⚠ 还有一处很容易写错、而且随机数据抓不到：字符要映射成 **1..26 而不是 0..25**。
//   映射成 0 的话 "a" 和 "aa" 的哈希都是 0 —— 见 wrongBase.cpp。

#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);

    string t, p;
    cin >> t >> p;
    int n = (int)t.size(), m = (int)p.size();

    /* ① 前缀哈希 + base 的幂（两套，两个模数各一套） */
    vector<long long> h1(n + 1, 0), h2(n + 1, 0), pw1(n + 1, 1), pw2(n + 1, 1);
    for (int i = 0; i < n; i++) {
        long long c = t[i] - 'a' + 1;             // ⚠ +1：不许有字符映射成 0
        h1[i + 1] = (h1[i] * B1 + c) % MOD1;
        h2[i + 1] = (h2[i] * B2 + c) % MOD2;
        pw1[i + 1] = pw1[i] * B1 % MOD1;
        pw2[i + 1] = pw2[i] * B2 % MOD2;
    }

    /* ② 取子串 t[l..r] 的哈希 —— 就是前缀和那一减 */
    auto sub = [&](int l, int r) {
        int len = r - l + 1;
        long long a = ((h1[r + 1] - h1[l] * pw1[len]) % MOD1 + MOD1) % MOD1;   // ⚠ +MOD 再取模
        long long b = ((h2[r + 1] - h2[l] * pw2[len]) % MOD2 + MOD2) % MOD2;
        return make_pair(a, b);
    };

    /* ③ 第一问：模式串出现在哪些位置（允许重叠） */
    long long g1 = 0, g2 = 0;
    for (char c : p) {
        g1 = (g1 * B1 + (c - 'a' + 1)) % MOD1;
        g2 = (g2 * B2 + (c - 'a' + 1)) % MOD2;
    }
    vector<int> pos;
    for (int i = 0; i + m <= n; i++) {
        pair<long long, long long> s = sub(i, i + m - 1);
        if (s.first == g1 && s.second == g2) pos.push_back(i);
    }
    cout << pos.size();
    for (int x : pos) cout << ' ' << x;
    cout << '\n';

    /* ④ 第二问：q 个询问，问 t 的两个子串相不相等 —— ★ KMP 做不了这件事，哈希 O(1) 就答 */
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (sub(l1, r1) == sub(l2, r2) ? "Y" : "N") << '\n';
    }
    return 0;
}