【学习记录】24.02.20 字符串

KSCD_ · 2024-02-20 11:16:19 · 个人记录

字符串算法

（感谢学长qwq）

Manacher

维护一个区间 [l,r]，表示 r 最大的中心在 i 之前的回文串，更新时：

• 若 i>r，暴力求解；
• 否则考虑 d_{l+r-i}，即回文串 [l,r] 中与 i 对应的那一位，令 z_i=\min(r-i+1,d_{l+r-i})。若用了 r-i+1 ，则继续向后暴力扩展；
• 最后必须用 i+z_i 尝试更新 r。

求长度为偶数的回文串可以用一个技巧，在两个字符之间均插入一个特殊字符，这样所有的回文串长度均为奇数。

P5446 [THUPC2018] 绿绿和串串

在速通，没听。

exKMP

维护一个区间 [l,r]，表示 r 最大的已匹配的区间，更新时：

• 若 i>r，暴力求解；
• 否则考虑 z_{i-l}，即 i 在 [l,r]中与 S 的前缀对应的那一位，令 z_i=\min(r-i+1,z_{i-l})。若用了 r-i+1 ，则继续向后暴力扩展；
• 最后必须用 i+z_i 尝试更新 r。

  P7114 [NOIP2020] 字符串匹配

  在自己理解，没听。

学长讲了个性质，对于字符串来说，后缀border以外的部分为该字符串最小周期。

做完以后发现一个性质，字符串非空的最小匹配前缀之外的部分为该字符串最大周期。

KMP

在求 s_i 时，尝试从 j=s_{i-1} 向后加一位，若不相等，则跳到 j=s_j 继续尝试，直到匹配到 S_j=S_i，记录 s_i=s_j+1。

P3435 [POI2006] OKR-Periods of Words

在听学长讲AC自动机，没听。

P2375 [NOI2014] 动物园

做过，在自己写笔记，没听。

P5829 【模板】失配树

出去了没听，但板子还是课后学一学吧。

对于KMP的 nxt 数组，建出一棵树，由 i 向 nxt_i 连边，这样的失配树与AC自动机中的 fail 树类似，是只有一个字符串的特殊情况。

HDU7138 String

还是没听。

KMP自动机

没听懂，后边再看Oiwiki吧。

P3193 [HNOI2008] GT考试

吃饭了不听了。

字典树

P2922 [USACO08DEC] Secret Message G

字典树维护，我以前写过，我写的方法是维护经过某节点的字符串数量和终止于某节点的字符串数量，简单容斥求解。

AC自动机

对于多个字符串，建出Trie后在Trie上求 fail 数组，表示这个点表示的字符串的最长后缀对应的节点。

若trie_{p,c}=u，则转移为：

• 若 trie_{fail_p,c} 存在，则 fail_u=trie_{fail_p,c}

• 否则不断令 p=fail_p，直到存在 trie_{fail_p,c}

这样维护出的 fail 数组是一棵树，后边还没深入。

P5357 【模板】AC 自动机

板子题。

P2414 [NOI2011] 阿狸的打字机

板子不会就放弃。

P3041 [USACO12JAN] Video Game G

板子不会就放弃。

P2444 [POI2000] 病毒

板子不会就放弃。

题目选讲

P5329 [SNOI2019] 字符串

要在 O(1) 的时间复杂度内比较，把整个字符串的比较转化为比较两字符串的不同部分。

真正看题解要做的时候发现，只要找到相邻两个字符的大小关系，就可以确定它们之前的大小关系，总复杂度为 O(n)。

P3426 [POI2005] SZA-Template

没咋认真听，但题解说应该是用KMP求出 nxt 数组，然后利用性质和dp求解。

P6216 回文匹配

KMP+Manacher+前缀和，不详细说了可以看题解。

CF1654F Minimal String Xoration

放弃了。