暑假作业做题记录（没写，待补）
蒟蒻挑战每一个专题最多只有一个作业不 AK……（不 AK 也要补起来 QwQ）\(2025.7.28 \sim 2025.7.29\) 字符串专题
\(Day 1\)
开幕雷击，一上来就是冷门的字符串。
今天是 trie、KMP、manacher、exKMP。
\(T1\) Best Cow Line G
本来想申请降绿但是不能工单调整相邻难度，后来有个学长帮忙降绿了但是被管理警告了。。。
考虑弱化版，每次显然能够选择较小的字母就选较小的那一端，难点是如果两端字母相同该怎么取。
其实也很好想，如果两端都相同，除了回文，必然存在一个长度 \(pos \le \lceil \frac{(tail - head + 1) }{2}\rceil\) 满足\(s_{} \neq s_{}\)，此时两端延伸出去的 \(pos\) 个位置的字符分别为 \(ch1\)，\(ch2\)，若 \(ch1 mx\) 则不符合我们的需求，需要 \(l\le mx\)，我们找到的第一个满足条件的 \(l\) 即为 \(|T|\)，输出 \(s_{}\)。
特别地，如果 \(l = 0\) 输出 Just a legend。
时间复杂度为 \(\mathcal O(n)\)。
\(T6\)，\(T7\)，\(T8\)，\(T9\)：对应模板 manacher、KMP、字典树、扩展 KMP/exKMP（Z 函数）。
因为是模板，因此此处省略：（
完成情况：AK。
\(Day 2\)
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]