洛谷 P4391 [BalticOI 2009] Radio Transmission 无线传输

// P4391 无线传输 —— 正解：答案 = n − nxt[n-1]，一行
//
// ★★ 两步就到：
//   ① 题面那句「S 是 S'+S'+… 的**子串**」⟺ **|S'| 是 S 的一个周期**
//      （周期 d 的定义：对所有 i ≥ d 有 s[i] == s[i−d]）。
//      · ⇐ 有周期 d ⇒ s[i] = s[i mod d] ⇒ S 就是 (前 d 个字符)^∞ 的前缀，当然是子串；
//      · ⇒ S'^∞ 整体有周期 d，而**子串继承周期** ⇒ S 有周期 d。
//      ⚠ 注意题面要的是「子串」不是「前缀」—— S' 不一定是 S 的前缀（`cabcabca` 的 S' 可以是 `abc`），
//        但**最短的那个长度是同一个**，所以不影响答案（p4391All.cpp 里全枚举验过）。
//   ② 最短周期 = **n − 最长 border**（border 和周期是一一对应的两种说法）。
//
// ⚠⚠ 而这道题最容易挂的地方，是把另一道经典题的写法搬过来：
//   「最小**整**周期」那类题（要求 d 整除 n）会多写一句 `if (n % d) d = n;`
//   —— 这道题**不要求整除**（样例 `cabcabca` 的答案就是 3，而 3 不整除 8）⇒ 那一句一加就错（见 p4391Div.cpp）。
#include <cstdio>
#include <cstring>
using namespace std;

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    if (scanf("%s", s) != 1) return 0;
    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;
    }
    printf("%d\n", n - nxt[n - 1]);
    return 0;
}

// P4391 —— 把题面那句「是 S'+S'+… 的**子串**」按字面全枚举验一遍。
//   ./p4391All        人话版
//   ./p4391All csv    给 check:viz 用
//
// ★★★ 为什么要有这一份：正解只有一行（`n − nxt[n-1]`），而它压着**两层推理**：
//   ① 「S 是某个长度 d 的串重复无限次的子串」⟺「d 是 S 的一个周期」；
//   ② 「最短周期」= 「n − 最长 border」。
//   ⇒ 两层都对才轮得到那一行。而[「验算要走一条和算法完全无关的路」](/sol/p1332/)——
//     这里走的是**最笨的那条**：把长度 d 的**候选串全枚举一遍**，
//     真的去查「S 是不是它重复若干次之后的子串」。
//
// ⚠ 顺带数一个决定这一页对拍档位的数：**有多少个串会让「整除版」出错**
//   （也就是 n 不被答案整除的那些）—— 那正是 p4391Div.cpp 的触发条件。
#include <bits/stdc++.h>
using namespace std;

static const int ALPHA = 2;                 // 字母表 {a, b}
static const int LMAX = 10;                 // 串长 1..10

static int byKmp(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;
    }
    return n - nxt[n - 1];
}
static int byPeriod(const string& s) {      // 按「周期」的定义
    int n = (int)s.size();
    for (int d = 1; d <= n; d++) {
        bool ok = true;
        for (int i = d; i < n && ok; i++) if (s[i] != s[i - d]) ok = false;
        if (ok) return d;
    }
    return n;
}
static int byLiteral(const string& s) {     // ★ 按题面**字面**：枚举候选 S'，查 S 是不是它的重复串的子串
    int n = (int)s.size();
    for (int d = 1; d <= n; d++) {
        int total = 1; for (int i = 0; i < d; i++) total *= ALPHA;
        for (int code = 0; code < total; code++) {
            string t;
            int c = code;
            for (int i = 0; i < d; i++) { t.push_back((char)('a' + c % ALPHA)); c /= ALPHA; }
            string rep;
            while ((int)rep.size() < n + d) rep += t;        // 重复到够长
            if (rep.find(s) != string::npos) return d;
        }
    }
    return n;
}

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

    long long total = 0, bad12 = 0, bad13 = 0, notDivide = 0, halfBorder = 0;
    for (int len = 1; len <= LMAX; len++) {
        long long cnt = 1;
        for (int i = 0; i < len; i++) cnt *= ALPHA;
        for (long long code = 0; code < cnt; code++) {
            string s;
            long long c = code;
            for (int i = 0; i < len; i++) { s.push_back((char)('a' + c % ALPHA)); c /= ALPHA; }
            total++;
            int a = byKmp(s), b = byPeriod(s), d = byLiteral(s);
            if (a != b) bad12++;
            if (a != d) bad13++;
            if (len % a) notDivide++;                        // ⇒ 「整除版」在这个串上会答错
            int nb = len - a;
            if (nb * 2 == len) halfBorder++;                 // ⇒ 「只打 border」那版恰好蒙对
        }
    }

    if (csv) {
        printf("total,%lld\nbadKmpPeriod,%lld\nbadKmpLiteral,%lld\n", total, bad12, bad13);
        printf("notDivide,%lld\nhalfBorder,%lld\n", notDivide, halfBorder);
        printf("pctNotDivide,%.2f\npctHalf,%.2f\n",
               100.0 * (double)notDivide / (double)total, 100.0 * (double)halfBorder / (double)total);
        return 0;
    }
    printf("① 字母表 {a,b}、长度 1~%d 的全部 %lld 个串，三种算法两两一致：\n", LMAX, total);
    printf("   n − 最长 border  ↔  按「周期」定义暴力      对不上 %lld 个\n", bad12);
    printf("   n − 最长 border  ↔  ★ 按题面**字面**全枚举候选 S'   对不上 %lld 个\n", bad13);
    printf("② 其中 n **不被**答案整除的有 %lld 个（%.2f%%）—— 「整除版」正是在这些串上答错\n",
           notDivide, 100.0 * (double)notDivide / (double)total);
    printf("③ 其中最长 border 恰好是一半的有 %lld 个（%.2f%%）—— 「只打 border」那版只在这些串上蒙对\n",
           halfBorder, 100.0 * (double)halfBorder / (double)total);
    return 0;
}

// P4391 ✗ 错法一：多写了一句「d 必须整除 n」
//
// ⚠⚠ 这是**另一道题的正确写法**：求「最小**整**周期」（把 S 恰好切成若干个相同的段）时，
//   `d = n − nxt[n-1]` 只有在 `n % d == 0` 时才是答案，否则整个串没有整周期、答案是 n。
//   那条判断在那类题上是必须的 —— ★ 而这道题**只要求 S 是 S'^∞ 的子串，不要求切得整齐**。
// ⇒ 官方样例一测就死：`cabcabca` 的 n = 8、d = 3，**3 不整除 8**，它会打出 8。
// ★ 触发条件：**n 不被 (n − nxt[n-1]) 整除**。
#include <cstdio>
#include <cstring>
using namespace std;

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

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    if (scanf("%s", s) != 1) return 0;
    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;
    }
    int d = n - nxt[n - 1];
    if (n % d) d = n;                       // ⚠ 这一句是「最小整周期」那道题的
    printf("%d\n", d);
    return 0;
}

// P4391 的生成器：./p4391Gen 种子 [档位]
//
// ★ 两个错法各靠什么现形：
//   · p4391Div（多写了「d 必须整除 n」）→ **n 不被答案整除**；
//   · p4391Nxt（直接打 border）        → **2 × nxt[n-1] ≠ n**（border 不是正好一半）。
//
// 档位：
//   0  ★ 顺手写的：26 个小写字母随机，n = 10~40（⚠ 几乎必然没有 border ⇒ 答案就是 n）
//   1  ⚠ 字母表压到 2 个（a / b）⇒ border 开始有了
//   2  ⚠⚠ **整周期串**：一小段重复整数次（n = d × k）
//      ⇒ ★ 那一档 `n % d == 0`，「整除版」那一句**根本不生效** ⇒ 它是**能证的精确的 0**
//   3  ★ 最终档：周期串 ＋ **随机截断**（n 不再整除 d）⇒ 「整除版」当场现形
//   4  ⚠⚠ 对照档：一段**正好重复两次**（`XX` 这种形状）⇒ 最长 border 恰好是一半
//      ⇒ ★★ 「整除版」和「只打 border」**同时**变成能证的精确的 0（两个 0 各有一行证明）
//
// ⚠ 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() % 5u;
        int d = 2 + (int)rd;                       // 一段的长度 2~6
        unsigned rk = rng() % 5u;
        int k = 3 + (int)rk;                       // 重复 3~7 次
        if (mode == 4) k = 2;                      // ⚠ 对照档：正好两次 ⇒ border = n/2
        string unit;
        for (;;) {                                 // 摇一段出来
            unit.clear();
            for (int i = 0; i < d; i++) unit.push_back(pick());
            if (mode != 4) break;
            /* ⚠ 档 4 要的是「border 恰好一半」，那要求这一段**自己没有更短的周期**
               （比如 unit = "aaa" 时，"aaaaaa" 的最长 border 是 5 而不是 3）*/
            bool primitive = true;
            for (int q = 1; q < d && primitive; q++) {
                if (d % q) continue;
                bool per = true;
                for (int i = q; i < d && per; i++) if (unit[(size_t)i] != unit[(size_t)(i - q)]) per = false;
                if (per) primitive = false;
            }
            if (primitive) break;
        }
        for (int i = 0; i < k; i++) s += unit;
        if (mode == 3) {                           // ⚠ 随机截断：n 不再是 d 的倍数
            unsigned rc = rng() % (unsigned)d;
            int cut = (int)rc;
            if (cut) s.resize(s.size() - (size_t)cut);
        }
    } 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;
}