洛谷 P3435 [POI 2006] OKR-Periods of Words

// P3435 OKR-Periods of Words —— 正解：每个前缀的最大周期 = 长度 − **最短非零 border**
//
// ★★ 先把题面那个「周期」翻译清楚（它和常说的「周期」差一个条件）：
//   题面：Q 是 A 的**真前缀**，且 A 是 **QQ** 的前缀。设 |A| = L、|Q| = q，那么
//   · 「A 是 QQ 的前缀」⇒ ① L ≤ 2q；② A 有通常意义的周期 q（即 A[i] = A[i−q]）。
//   · 「真前缀」⇒ 0 < q < L。
//   而周期 q ⟺ border b = L − q ⇒ 三个条件合起来就是：**0 < b ≤ L/2**。
//   ⇒ 要最大的 q，就是要**最小的非零 border**。
// ★ 而「最短非零 border 一定 ≤ L/2」是白送的：若 b > L/2，那条 border 自己重叠，
//   于是 2b − L 也是一个更短的非零 border ⇒ 最短的那个不可能 > L/2。
//
// ⚠⚠ 这里和[同一张题单的 P4391](/sol/p4391/) **正好相反**：那道题要的是 **n − 最长 border**。
//   ⇒ 同一个 next 数组，两道题往两个方向用（见 p3435Long.cpp —— 那一版就是把这道题当成了那道题）。
//
// ★ 求「最短非零 border」不用跳链，一条递推就够（O(n)）：
//   f[i] = s[0..i] 的最短非零 border 长度（没有就是 0）
//        = nxt[i] == 0            ? 0
//        : f[nxt[i]-1] != 0       ? f[nxt[i]-1]     // border 的 border 更短
//        : nxt[i];                                  // nxt[i] 自己就是最短的那个
// ⚠ 答案顶格 ≈ n²/2 = 5×10¹¹ ⇒ **必须 long long**（见 p3435Int.cpp，那条线正好在 n = 65537）。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static char s[MAXN];
static int nxt[MAXN], f[MAXN];

int main() {
    int k;
    if (scanf("%d", &k) != 1) return 0;
    if (scanf("%s", s) != 1) return 0;
    int n = (int)strlen(s);
    nxt[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;
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int b = nxt[i];
        if (b == 0) f[i] = 0;
        else f[i] = f[b - 1] ? f[b - 1] : b;
        if (f[i]) ans += (long long)(i + 1) - f[i];   // 没有非零 border ⇒ 周期是空串，加 0
    }
    printf("%lld\n", ans);
    return 0;
}

// P3435 ✗ 错法一：用了**最长** border —— 那是隔壁 P4391 的写法
//
// ⚠⚠ 同一个 next 数组，两道题往**相反**的方向用：
//   · [P4391](/sol/p4391/)：要**最短周期** = n − **最长** border；
//   · 本题：      要**最大周期** = L − **最短非零** border。
// ⇒ 顺手写成 `ans += (i+1) - nxt[i]`，算出来的是**每个前缀的最小周期之和**。
// ★ 触发条件：**存在某个前缀，它的最长 border 和最短非零 border 不是同一个**
//   （也就是 border 链长度 ≥ 2）。⇒ 官方样例 `babababa` 一测就死（24 → 20）。
#include <cstdio>
#include <cstring>
using namespace std;

static const int MAXN = 1000006;
static char s[MAXN];
static int nxt[MAXN];

int main() {
    int k;
    if (scanf("%d", &k) != 1) return 0;
    if (scanf("%s", s) != 1) return 0;
    int n = (int)strlen(s);
    nxt[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;
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) if (nxt[i]) ans += (long long)(i + 1) - nxt[i];   // ⚠ 最长而不是最短
    printf("%lld\n", ans);
    return 0;
}

// P3435 解析页上那几个「对拍看不见」的数字的出处。
//   ./p3435Count        人话版
//   ./p3435Count csv    给 check:viz 用
//
// 它回答三件事：
//   ① ★ **`int` 那条线在哪** —— 全是同一个字母时答案是 n(n−1)/2，第一次越过 2³¹−1 的 n 是多少。
//      ⚠ 这里**只负责算**；确认那一步交给 `check:viz`：拿真程序在 n = 65536 / 65537 上
//        各跑一遍，看 int 版是不是**正好**在 65537 开始和正解不一样。
//        （拿同一个公式再算一遍不叫自检 —— [第 19 章 P2240](/sol/p2240/) 那条。）
//   ② 顶格（n = 10⁶）的答案有多大、是 `int` 上限的多少倍；
//   ③ ★★★ 「沿 border 链一路跳到底」那一版**跳了多少步** ——
//      它的答案永远对，对拍看不见，**只能换尺子数次数**
//      （[第 20 章 P5019](/sol/p5019/) 那条：n 每翻 4 倍，O(n²) 的签名是次数 ×16）。
#include <bits/stdc++.h>
using namespace std;

/** 全 a 串上，「一路跳到底」要跳多少步 */
static long long jumpSteps(const string& s) {
    int n = (int)s.size();
    vector<int> nxt(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;
    }
    long long steps = 0;
    for (int i = 0; i < n; i++) {
        int j = nxt[i];
        if (!j) continue;
        while (nxt[j - 1]) { j = nxt[j - 1]; steps++; }
    }
    return steps;
}
/** 正解那一版（一句递推）只花几步 —— 每个下标恰好一次 */
static long long recurSteps(const string& s) { return (long long)s.size(); }

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

    /* ① int 那条线：算出来 + 穷举确认 */
    long long INTMAX = 2147483647LL;
    int lineCalc = 0;
    for (long long n = 1; n <= 200000; n++)
        if (n * (n - 1) / 2 > INTMAX) { lineCalc = (int)n; break; }
    long long atLine = (long long)lineCalc * (lineCalc - 1) / 2;
    long long belowLine = (long long)(lineCalc - 1) * (lineCalc - 2) / 2;

    /* ② 顶格 */
    long long big = 1000000LL * (1000000LL - 1) / 2;

    /* ③ 跳链步数：全 a 串 vs 随机串 */
    mt19937 rng(20260908u);
    vector<int> NS = {1000, 4000, 16000};
    vector<long long> stepA, stepR;
    for (int n : NS) {
        stepA.push_back(jumpSteps(string((size_t)n, 'a')));
        string r;
        for (int i = 0; i < n; i++) { unsigned c = rng() % 26u; r.push_back((char)('a' + c)); }
        stepR.push_back(jumpSteps(r));
    }

    if (csv) {
        printf("lineCalc,%d\natLine,%lld\nbelowLine,%lld\n", lineCalc, atLine, belowLine);
        printf("big,%lld\novInt,%.0f\n", big, (double)big / (double)INTMAX);
        for (size_t i = 0; i < NS.size(); i++) printf("stepA%d,%lld\n", NS[(int)i], stepA[i]);
        for (size_t i = 0; i < NS.size(); i++) printf("stepR%d,%lld\n", NS[(int)i], stepR[i]);
        printf("ratioA1,%.1f\nratioA2,%.1f\n",
               (double)stepA[1] / (double)stepA[0], (double)stepA[2] / (double)stepA[1]);
        printf("recur,%lld\n", recurSteps(string(16000, 'a')));
        return 0;
    }

    printf("① int 那条线：全 a 串的答案 n(n−1)/2 第一次越过 2³¹−1 是在 n = %d\n", lineCalc);
    printf("   （n = %d 时 %lld ≤ 2147483647，n = %d 时 %lld > 它）\n",
           lineCalc - 1, belowLine, lineCalc, atLine);
    printf("   ⚠ 这只是算出来的；确认那一步在 check:viz 里：拿真程序在这两个 n 上各跑一遍\n");
    printf("   ⇒ 和第 11 章 P1908、第 35 章 P2866 的那条线一模一样 —— 它是 int 的性质\n");
    printf("② 顶格 n = 10⁶：答案 %lld，是 int 上限的 %.0f 倍\n", big, (double)big / (double)INTMAX);
    printf("③ 「一路跳到底」跳了多少步（全 a 串 ／ 随机串）：\n");
    for (size_t i = 0; i < NS.size(); i++)
        printf("   n = %5d：全 a %12lld 步   随机 %6lld 步\n", NS[(int)i], stepA[i], stepR[i]);
    printf("   n 每翻 4 倍，全 a 那一列 ×%.1f、×%.1f —— 这就是 O(n²) 的签名\n",
           (double)stepA[1] / (double)stepA[0], (double)stepA[2] / (double)stepA[1]);
    printf("   ★ 而正解那一句递推：每个下标恰好走一次，n = 16000 就是 %lld 步\n", recurSteps(string(16000, 'a')));
    return 0;
}

// P3435 的生成器：./p3435Gen 种子 [档位]
//
// ★ 四个待测版本里，**只有一个是对拍抓得到的**：
//   · p3435Long（用了最长 border）→ **存在某个前缀，它的 border 链长度 ≥ 2**
//     （也就是「最长 border」和「最短非零 border」不是同一个）；
//   · p3435Int（答案用 int）→ ⚠ 要答案越过 2³¹，那条线在 **n = 65537**
//     ⇒ **小数据结构上到不了** ⇒ 对拍四档全是 0；
//   · p3435Jump（沿链一路跳到底）→ ⚠ **答案永远对** ⇒ 对拍原理上看不见。
//   ⇒ ★★ 两种「对拍是聋的」，理由完全不同：一个是「答案永远对」，一个是「档位到不了那条线」。
//
// 档位：
//   0  ★ 顺手写的：26 个小写字母随机，n = 10~40（⚠ border 链几乎全是空的 ⇒ Long 版蒙对）
//   1  ⚠ 字母表压到 2 个（a / b）
//   2  ⚠ 周期串：一小段重复若干次 ⇒ border 链一下子变长
//   3  ★ 最终档：周期串 ＋ 随机尾巴
//
// ⚠ 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); };

    string s;
    if (mode >= 2) {
        unsigned rd = rng() % 3u;
        int d = 1 + (int)rd;                       // 一段 1~3 个字符 ⇒ border 链长
        unsigned rk = rng() % 8u;
        int k = 4 + (int)rk;
        string unit;
        for (int i = 0; i < d; i++) unit.push_back(pick());
        for (int i = 0; i < k; i++) s += unit;
        if (mode == 3) {                           // 随机尾巴
            unsigned rt = rng() % 6u;
            int t = (int)rt;
            for (int i = 0; i < t; i++) s.push_back(pick());
        }
    } else {
        unsigned r = rng() % 31u;
        int n = 10 + (int)r;
        for (int i = 0; i < n; i++) s.push_back(pick());
    }
    printf("%d\n%s\n", (int)s.size(), s.c_str());
    return 0;
}