字符串合集

坚持一个字符串算法原则：世界上只有一个字符串算法。
下文中的字符串均为 1-index。

KMP

求出 $nxt$ 数组，$nxt_i$ 表示以 $i$ 结尾的串的最长公共前后缀长度。

for(int i=2,j=0;i<=n;i++){
    while(j&&s[j+1]!=s[i]) j=nxt[j];
    if(s[j+1]==s[i]) ++j;
    nxt[i]=j;
}

[POI 2005] SZA-Template

设 $f_i$ 表示长度为 $i$ 的前缀需要的最短印章长度，$g_i$ 为长度为 $i$ 的印章可以覆盖到的最远的位置，显然 $f_i$ 可以等于 $i$。考虑找更优的方案，也就是寻找一个 $j$ 使得 $f_i=f_j$。我们发现，若 $f_{nxt_i}$ 的印章可以覆盖到 $i-nxt_i$，则可以在 $i-nxt_i$ 处再盖一次到达 $i$。所以若 $g_{f_{nxt_i}}\ge i-nxt_i$，就可以用 $f_{nxt_i}$ 更新 $f_i$。

「KTSC 2020 R1」字符串查找

考虑变换一下匹配时判断字符是否相等的条件：记录每个字符到它的前驱的距离，特判第一次出现即可。

字符串哈希

套上二分就可以完成绝大部分字符串问题。万金油了属于是。

[NOI2017] 蚯蚓排队

注意到 $k$ 较小，所以我们可以暴力维护长度小于等于 $k$ 的子串的哈希值，合并和分裂直接用链表维护，每次暴力在哈希表里增删即可。

Trie

[IOI 2008] Type Printer

将所有串插入 Trie 中，则遍历 Trie 的过程就是打印的一种方案，一个结论是：我们遍历时最后遍历 Trie 上的最长链可以得到最小操作次数。

超超的序列 加强

将下标看作二进制串，发现就是要维护支持区间修改和查询的、在叶子节点存储原序列信息的 01Trie，仿照线段树的写法写 push down 和 push up 即可。写长得像 Trie 的线段树和长得像线段树的 Trie 均可。

Manacher

求解回文串问题。
设 $[l,r]$ 表示下标在 $l,r$ 之间的字串。
只考虑奇回文串：
$p_i$ 表示以 $i$ 为中心的最长回文半径，$r$ 为当前覆盖位置最靠右的回文串能覆盖到的最大下标，$mid$ 表示它的回文中心的下标。设当前考虑到第 $i$ 个字符：

• $i>r$ 时，直接暴力向后跳；
• $i\le r$ 时，设 $j$ 为 $i$ 关于 $mid$ 的对称点，即 $j=mid\times 2-i$；
  由于 $[j-p_j,j+p_j]$ 与 $[i-p_i,i+p_i]$ 相等且都是回文串，所以 $p_i$ 可以直接取 $p_j$ 的值。但是这个推论成立当且仅当 $i+p_j\le r$，否则 $p_i$ 最大只能取到 $r-i+1$，然后再暴力扩展。
  故 $p_i=\min(p_j,r-i+1)$。
  同时动态更新 $r$ 和 $mid$ 即可。

for(int i=1,r=0,mid=0;i<=n;i++){
    int j=2*mid-i;
    if(i<=r) p[i]=min(r-i+1,p[j]);
    else p[i]=1;
    while(s[i-p[i]]==s[i+p[i]]) ++p[i];
    if(i+p[i]-1>r){
        r=i+p[i]-1;
        mid=i;
    }
}

AC 自动机

可以实现更强力的字符串匹配。核心思想是在 Trie 上添加失配指针使得失配时可以快速找到下一个匹配的位置，也就是最长公共前后缀。失配指针形成的树形结构称作 fail 树。Trie 是外向树而 fail 树是内向树。使用拓扑排序优化后可以实现 $O(n)$ 多模式串匹配，$n$ 为文本串长度。

void build(){
    queue<int> q;
    for(int i=0;i<26;i++)
        if(nxt[0][i]) q.push(nxt[0][i]);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(nxt[u][i]){
                fail[nxt[u][i]]=nxt[fail[u]][i];
                q.push(nxt[u][i]);
            }
            else nxt[u][i]=nxt[fail[u]][i];
        }
    }
}

[COCI 2014/2015 #5] Divljak

先将所有 $S$ 建成 ACam 并建出 fail 树，对于加入集合的一个串 $P$，在 ACam 上遍历到每个节点时我们先令这个节点在 fail 树上到根链加 $1$，发现这样肯定会算重，我们可以将所有遍历到的节点按 fail 树 dfn 排序，每次令第 $i$ 和第 $i+1$ 个点的 LCA 到根链减 $1$ 即可消去重复贡献，可以树上差分转为单点加+子树求和，树状数组维护即可。

[CSP-S 2025] 谐音替换

将所有字符串二元组转化为：最长公共前缀+分隔符+1 串中间不同部分+2 串中间不同部分+分隔符+最长公共后缀，然后对于每组询问在 ACam 上多模式串匹配，匹配数即为答案。

存在 Trie+二维数点做法。

[JOI Open 2016] 销售基因链 / Selling RNA Strands

与上一道题几乎一样。

其他好题

[POI 2012] PRE-Prefixuffix

容易发现两个串循环同构当且仅当其能被表示为形如 $AB$ 和 $BA$，则我们要做的事情就是尝试将原串划分为形如 $ABCBA$ 的串。
一个自然的想法是枚举 $B$ 的起点然后尝试求解 $B$ 的长度。设 $i$ 为起点时的答案为 $f_i$，也就是 $s[i,n-i+1]$ 的 border（当然要满足 $i+f_i\le\dfrac{n}{2}$），现在来思考 $s[i+1,n-i]$ 对应的 $f_{i+1}$，注意到它的 border 最长只能是 $s[i,n-i+1]$ 的 border 去掉头尾，故 $f_i\le f_{i+1}+2$，所以我们可以从大到小枚举 $i$，由于每次 $f_i$ 到 $f_{i-1}$ 答案最多加 $2$，所以我们可以直接暴力匹配。