Timus 1723 Sandro's Book：最強子串（KMP 暴力枚舉 / 單字符統計）

問題描述

給定字符串 S (|S| ≤ 50)，定義「咒語」為 S 的任意子串（連續）。咒語的「力量」= 它在 S 中出現的次數（可重疊）。求力量最大的咒語（任意輸出一個）。

樣例

輸入：tebidohtebidoh
輸出：tebidoh

「tebidoh」出現 2 次，力量 2。

方法一：KMP 暴力枚舉所有子串（AC 但過度設計）

• 枚舉所有 O(n²) 子串。
• 對每個子串用 KMP 在 S 中計數出現次數（含重疊）。
• 記錄最大力量及對應子串。
• 複雜度：O(n³)，n=50 時 125,000 操作，極快 AC。

方法二：單字符統計（真正的預期解 / 題目陷阱）

子串包含長度為 1 的字符！
單字符 c 的力量 = c 在 S 中出現的次數。
任意長度 ≥ 2 的子串出現次數 ≤ 其首字符出現次數。
因此 最大力量必由某個單字符達成！

算法：統計 26 個小寫字母頻率，輸出頻率最高的字母。
樣例 tebidohtebidoh 中 't','e','b','i','d','o','h' 各 2 次，輸出任意一個均正確。

代碼對比

// 方法一：KMP 暴力（複雜但通用）
// 方法二：單字符統計（極簡）
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    int cnt[26] = {}, best = 0, maxc = 0;
    for (char c : s) if (++cnt[c-'a'] > maxc) { maxc = cnt[c-'a']; best = c-'a'; }
    cout << char('a' + best) << "\n";
    return 0;
}

深刻教訓

1. 仔細讀題：「任意子串」包含長度 1，題目未排除。
2. 數學洞察：長子串出現次數受限於其組成字符頻率，單字符統計已涵蓋最優解。
3. 不要過度工程：KMP 版雖 AC，但屬於「用大炮打蚊子」，且在面試/比賽中會被視為未發現最優解。

總結

Timus 1723 表面是字符串模式匹配，實則是讀題細節 + 數學觀察的陷阱題。最優解僅需 O(n) 統計字符頻率。此類「看似複雜實則簡單」的題目在 ACM/ICPC 中常見，訓練「先思考最簡單模型是否適用」的習慣極其重要。