洛谷 P2375 [NOI2014] 动物园

// P2375 [NOI2014] 动物园 —— 正解：两个指针，一趟 O(L)
//
// ★★ 题面要的 num[i]：s 的前 i 个字符里，「既是前缀又是后缀、**而且两段不重叠**」的串有几个。
//   翻译过来就是：**长度 ≤ i/2 的非空 border 有几个。**
//
// ★ 拆成两半，每一半都只要一句话：
//   ① **border 链的长度**能递推：cnt[i] = s[0..i] 的非空 border 个数
//      = cnt[nxt[i]-1] + 1（nxt[i] > 0 时），否则 0。
//      —— 因为「border 的 border 还是 border」，整条链就是一棵树上的一条路径。
//   ② **「长度 ≤ 一半」那个限制**只要再养一个指针 k：它像 KMP 一样跟着 i 往前走，
//      走完再 `while (2k > i+1) k = nxt[k-1]` 缩回来。
//      ⇒ k 只增不减地往前走、每次回退至少减一 ⇒ **两个指针都是均摊 O(1)**，整体 O(L)。
//   最后 num[i] = k > 0 ? cnt[k-1] + 1 : 0（长度 ≤ k 的 border 就是「k 自己 ＋ k 那个前缀的全部 border」）。
//
// ⚠ 三个容易漏的角：
//   · 「不重叠」那半漏掉 ⇒ 变成 cnt[i]（见 p2375Overlap.cpp）；
//   · 那个 k 不用均摊指针、每个 i 都从头跳 ⇒ O(L²)，**答案对但跑不完**（见 p2375Chain.cpp）；
//   · **多测**：答案累乘的变量每组都要重置（见 p2375Ans.cpp）。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static const long long MOD = 1000000007LL;
static char s[MAXN];
static int nxt[MAXN], cnt[MAXN];

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        if (scanf("%s", s) != 1) return 0;
        int n = (int)strlen(s);
        nxt[0] = 0;
        cnt[0] = 0;
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && s[i] != s[j]) j = nxt[j - 1];
            if (s[i] == s[j]) j++;
            nxt[i] = j;
            cnt[i] = j ? cnt[j - 1] + 1 : 0;
        }
        long long ans = 1;                          // ⚠ 每组都要重置
        for (int i = 1, k = 0; i < n; i++) {
            while (k > 0 && s[i] != s[k]) k = nxt[k - 1];
            if (s[i] == s[k]) k++;
            while (k > 0 && 2 * k > i + 1) k = nxt[k - 1];    // ★ 缩到「不重叠」为止
            long long num = k ? cnt[k - 1] + 1 : 0;
            ans = ans * ((num + 1) % MOD) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

// P2375 ✗ 错法一：漏掉了「这个后缀与这个前缀**不重叠**」
//
// ⚠ 题面把这句话说了两遍，还专门举了例子：`S = aaaaa` 时 `num[4] = 2`，
//   因为 `aaa` 虽然既是前缀又是后缀，**但两段重叠了**，不算。
// ⇒ 漏掉这半句，num[i] 就变成了「**所有**非空 border 的个数」= cnt[i]。
// ★ 触发条件：**存在某个前缀，它有长度 > 一半的 border**
//   —— 也就是那个前缀「自己叠在自己身上」。⇒ 官方样例第一组（`aaaaa`）一测就死。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static const long long MOD = 1000000007LL;
static char s[MAXN];
static int nxt[MAXN], cnt[MAXN];

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;
    while (T--) {
        if (scanf("%s", s) != 1) return 0;
        int n = (int)strlen(s);
        nxt[0] = 0; cnt[0] = 0;
        for (int i = 1, j = 0; i < n; i++) {
            while (j > 0 && s[i] != s[j]) j = nxt[j - 1];
            if (s[i] == s[j]) j++;
            nxt[i] = j;
            cnt[i] = j ? cnt[j - 1] + 1 : 0;
        }
        long long ans = 1;
        for (int i = 1; i < n; i++) {
            long long num = cnt[i];                  // ⚠ 所有 border，没管重不重叠
            ans = ans * ((num + 1) % MOD) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

// P2375 解析页上那几个「对拍看不见」的数字的出处。
//   ./p2375Count        人话版
//   ./p2375Count csv    给 check:viz 用
//
// ★★ 这道题唯一一个对拍抓不到的错法是「那个 k 每轮都从头跳」——它**答案永远对**，
//   ⇒ 只能[换尺子数次数](/ch/48-kmp/)。这里数的是「k 一共回退了多少步」：
//   · 正解：k 只增不减地往前走，回退总数**均摊 O(L)**；
//   · 跳链版：每个 i 都从 nxt[i] 重新往下跳 ⇒ 全是同一个字母时是 **O(L²)**。
// ⚠ 而随机串上两者几乎一样 —— **顺手造一组顶格随机跑一遍，这个坑一步都看不见。**
#include <bits/stdc++.h>
using namespace std;

static void build(const string& s, vector<int>& nxt) {
    int n = (int)s.size();
    nxt.assign(n, 0);
    for (int i = 1, j = 0; i < n; i++) {
        while (j > 0 && s[i] != s[j]) j = nxt[j - 1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }
}
/** 正解那个均摊指针：一共回退多少步 */
static long long stepsAmortized(const string& s) {
    int n = (int)s.size();
    vector<int> nxt;
    build(s, nxt);
    long long steps = 0;
    for (int i = 1, k = 0; i < n; i++) {
        while (k > 0 && s[i] != s[k]) { k = nxt[k - 1]; steps++; }
        if (s[i] == s[k]) k++;
        while (k > 0 && 2 * k > i + 1) { k = nxt[k - 1]; steps++; }
    }
    return steps;
}
/** 跳链版：每个 i 都从 nxt[i] 重新往下跳 */
static long long stepsRestart(const string& s) {
    int n = (int)s.size();
    vector<int> nxt;
    build(s, nxt);
    long long steps = 0;
    for (int i = 1; i < n; i++) {
        int k = nxt[i];
        while (k > 0 && 2 * k > i + 1) { k = nxt[k - 1]; steps++; }
    }
    return steps;
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";
    mt19937 rng(20260908u);
    vector<int> NS = {1000, 4000, 16000};
    vector<long long> amoA, resA, resR;
    for (int n : NS) {
        string a((size_t)n, 'a');
        amoA.push_back(stepsAmortized(a));
        resA.push_back(stepsRestart(a));
        string r;
        for (int i = 0; i < n; i++) { unsigned c = rng() % 26u; r.push_back((char)('a' + c)); }
        resR.push_back(stepsRestart(r));
    }
    /* 顶格输入有多大：5 组 × 10⁶ 个字符 */
    long long inBytes = 5LL * 1000000 + 5 + 2;

    if (csv) {
        for (size_t i = 0; i < NS.size(); i++) printf("amoA%d,%lld\n", NS[(int)i], amoA[i]);
        for (size_t i = 0; i < NS.size(); i++) printf("resA%d,%lld\n", NS[(int)i], resA[i]);
        for (size_t i = 0; i < NS.size(); i++) printf("resR%d,%lld\n", NS[(int)i], resR[i]);
        printf("ratioRes1,%.1f\nratioRes2,%.1f\n",
               (double)resA[1] / (double)resA[0], (double)resA[2] / (double)resA[1]);
        printf("ratioAmo1,%.1f\nratioAmo2,%.1f\n",
               (double)amoA[1] / (double)amoA[0], (double)amoA[2] / (double)amoA[1]);
        printf("inBytes,%lld\n", inBytes);
        return 0;
    }
    printf("「k 一共回退了多少步」（全是 a 的串 ／ 随机 26 个字母）：\n");
    printf("   %8s %14s %14s %14s\n", "n", "正解(均摊)", "跳链版(全a)", "跳链版(随机)");
    for (size_t i = 0; i < NS.size(); i++)
        printf("   %8d %14lld %14lld %14lld\n", NS[(int)i], amoA[i], resA[i], resR[i]);
    printf("   n 每翻 4 倍：正解 ×%.1f ×%.1f（线性）；跳链版 ×%.1f ×%.1f（★ O(n²) 的签名）\n",
           (double)amoA[1] / (double)amoA[0], (double)amoA[2] / (double)amoA[1],
           (double)resA[1] / (double)resA[0], (double)resA[2] / (double)resA[1]);
    printf("⇒ 顶格 L = 10⁶ 时跳链版约 2.5 × 10¹¹ 步；而顶格输入本身有 %lld 字节（5 组 × 10⁶）\n", inBytes);
    return 0;
}

// P2375 的生成器：./p2375Gen 种子 [档位]
//
// ★ 三个待测版本各靠什么现形：
//   · p2375Overlap（漏掉「不重叠」）→ **存在某个前缀，它的最长 border 超过了一半**
//     （也就是 `2 × nxt[i] > i+1`）；
//   · p2375Ans（答案没每组重置）    → **组数 ≥ 2，而且前面某组的答案不是 1**；
//   · p2375Chain（k 每轮从头跳）    → ⚠ **答案永远对**，对拍原理上看不见。
//
// 档位：
//   0  ★ 顺手写的：**一组**，26 个小写字母随机，L = 10~40
//      ⚠ 这一档同时把两个错法打成 0：随机串几乎没有 border（Overlap 抓不到），
//        而且**只有一组**（Ans 结构上不可能现形）
//   1  ⚠ 字母表压到 2 个
//   2  ⚠ 周期串：一小段重复若干次 ⇒ 长 border 满地都是
//   3  ★ 最终档：**2~5 组** ＋ 周期串
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 1000003u + 20260908u);

    int alpha = (mode >= 1) ? 2 : 26;
    auto pick = [&]() { unsigned r = rng() % (unsigned)alpha; return (char)('a' + r); };

    int T = 1;
    if (mode == 3) { unsigned rt = rng() % 4u; T = 2 + (int)rt; }
    printf("%d\n", T);
    for (int t = 0; t < T; t++) {
        string s;
        if (mode >= 2) {
            unsigned rd = rng() % 3u;
            int d = 1 + (int)rd;
            unsigned rk = rng() % 8u;
            int k = 3 + (int)rk;
            string unit;
            for (int i = 0; i < d; i++) unit.push_back(pick());
            for (int i = 0; i < k; i++) s += unit;
        } else {
            unsigned r = rng() % 31u;
            int n = 10 + (int)r;
            for (int i = 0; i < n; i++) s.push_back(pick());
        }
        printf("%s\n", s.c_str());
    }
    return 0;
}