集训之字符串专题

A

题意简述

给你一个长度为 $nk$ 的字符串，再给你 $n$ 个长度为 $k$ 的字符串片段，需要你重新排列这些字符串片段，定义一个排列的值为每个片段匹配原串的最长前缀之和，求所有可能的排列中的最大值。

题目分析

可以先把原来的字符串分成 $n$ 份再插入 trie 树中，再将每个字符串片段在 trie 树上遍历一遍，记录可以到达的最后位置。

剩下即是思考求解最大值。

考虑贪心，可以发现先将片段匹配最长的一定是最优的，但关键是如何处理原串同一个位置不被多次匹配。可以考虑在建立 trie 树时记录每个点被经过几次，用 cnt 数组表示（当前位置最多可以被匹配几次）。将所有片段最后匹配位置丢进大根堆中（层排序），然后每次取出堆顶，判断当前点经过次数 cnt 是否仍大于 0，如果大于 0，则可行，加上层数贡献，然后往上 cnt 都减去 1；否则跳父亲到第一个 cnt 大于 0 的点，为了保证正确性，再将此点丢尽堆中。

while (q.size()) {
    int u = q.top();
    q.pop();
    if (cnt[u]) {
        int p = u;
        while (p) {
            cnt[p]--;
            p = fa[p];
        }
        ans += dep[u];
    }
    else {
        int p = u;
        while (p && !cnt[p]) {
            p = fa[p];
        }
        if (p) {
            q.push(p);
        }
    }
}

B

题意简述

给你一个字符串 S，包含小写字母和问号，再给你一个模式串 T，你需要将问号换成小写字母，使得 T 匹配次数尽可能多，求可能的最多的匹配次数。

题目分析

考虑 DP，用 $f_i$ 表示 S 长度为 $i$ 时最多的匹配次数，考虑如何转移，一个是当前 $i$ 不会产生贡献，直接从 $f_{i - 1}$ 转移即可，一个是当前 $i$ 可能产生贡献，此时 S 以 $i$ 结尾的后缀一定可以表示成 T。而且值得注意的是，当后缀为 T 时，产生的贡献可能不止为 1（因为有重叠部分）。所以需要 $g$ 数组辅助，定义 $g_i$ 为长度为 $i$ 时字符串以 T 结尾时的最大匹配次数。

考虑 $g$ 的递推。首先令 $g_i = f_{i - len_T}$，代表当前结尾贡献没计算时至少匹配多少次，然后考虑重叠的影响（先用 KMP 算出可以前后可以重叠的有哪些长度），令可以重叠的长度为 l，遍历 l，从 $g_{i - (len_T - l)}$ 中取最大值转移。最后加上自身的贡献 1 即是 $g_i$。最后再从 $g_i$ 转移到 $f_i$ 即可。

for (int i = 1; i <= len1; ++i) {
    f[i] = f[i - 1];
    if (check(i)) {
        g[i] = f[i - len2];
        for (int j = nxt[len2]; j; j = nxt[j]) {
            g[i] = max(g[i], g[i - (len2 - j)]);
        }
        g[i] += 1;
        f[i] = max(f[i], g[i]);
    }
}

C

题意简述

求一个字符串的最小表示法。即求一个字符串的所有循环同构串中的字典序最小的一个。

题目分析

暴力显然会超时，考虑优化。

定义两个指针 $i, j$，再定义 $k$，表示从 $S_{i..i + k - 1}$ 和 $S_{j..j + k - 1}$ 相等。优化关键在于如果我们发现 $S_{i +k} < S_{j + k}$，则以 $j..j + k$ 开头的字符串一定没有贡献，因为以 $i..i + k$ 开头的字符串时更优的。所以可以令 $j = j + k + 1$。如果 $i = j$ 则再令 $j = j + 1$ 即可。

我们发现 $i, j$ 都至多移动 $n$ 次，而 $k$ 实际上就是 $i, j$ 移动多少的度量，其和不超过 $2n$ 次，所以算法复杂度是 $O(n)$ 的。

D

题意简述

求主串 S 中模式串 T 的出现次数。

题目分析

KMP 模板题。

定义 $f_i$ 为长度为 $i$ 时，最长公共前缀后缀的长度（不包括本身）。令 SS = T + ' ' + S，然后跑 KMP 求出 f 数组即可，当有 $f_i$ 为 $len_T$ 时，答案就加一即可。

E

题意简述

有一个字符串 S，和一个空字符串 T，你每次可以从 S 的首或尾取出一个字符加入到 T 的结尾处，求字典序最小的 T。

题目分析

当 $S$ 首尾不同时，显然是取字符最小的。推广一下，即是取字典序最小的一端（原串与逆串比较）。

现在问题是如何快速求首尾哪个字符串的字典序更小，考虑二分加哈希。

先首尾各自哈希一遍，然后二分第一个不同位置，然后比较不同位置的字母大小即可。

F

题意简述

给定一个字符串 $S$，求它的第 $k$ 小子串，需要分不同位置的相同子串为一个或多个来分别考虑。

题目分析

SAM 模板题。

先考虑算作一个的情况，此时所有点的权值都设为 1，代表并不会计算重复；若是算作多个，则需将权值设为 endpos 集合的大小，只需要在 parent 树上 dfs 统计一下子树内所有非克隆结点结点的个数。

将点设好权值好，我们再 dfs 计算一颗子树内的权值。剩下找第 $k$ 大即是在 sam 上试探着走点即可。

J

题意简述

给你多个模式串 T 和一个匹配串 S，求每个模式串在匹配串的出现次数。

题目分析

多个模式串，AC 自动机模板题。对模式串建立 AC 自动机，然后跑一遍匹配串即可。

L

题意简述

给你一个字符串 S，求添加多少个字符能变得有一个非自身的循环节。

题目分析

套结论即可。求出 S 最后一个点的 nxt 大小，令为 $x$，若 len % (len - x) == 0，则代表已经有循环节，可以不添加。否则 len % (len - x) 即是期望循环节的大小。

M

题意简述

给你 $n$ 个 01 串，求最长的的 01 串 S 不包含任意一个给定 01 串（多个最长取字典序最小），或者判断 S 可以无限长。

题目分析

建立 AC 自动机。给每个 01 串的结尾结点标记（同时要标记 fail 失配树的儿子结点），首先判断能不经过标记结点形成一个环，若能，则代表可以无限长。若不能即是求最长不经过标记结点的路径长度，这个东西 dfs 一遍，求一下每个结点最远到达长度即可。输出方案记录一下从哪里转移即可。

N

题意简述

给你一个字符串 S 和 $q$ 次询问，每次询问给你两个长度相同的区间，问是否存在一种字母表的一一映射方案，使得能从一个区间映射到另一个区间。

题目分析

即是需要快速判断是否存在一种方案使得能够一一映射，发现如果存在，那么对应字母的位置信息是相同的。所以想到将每个字母的出现位置都存在哈希数组里面。判断是否可行，只需要一个区间的 26 个字母信息丢到一个数组里面，另一个区间的 26 个字母信息丢到另一个数组里面，判断这两个集合是否相等即可。

O

题意简述

给你一颗 $n$ 个结点的树，你可以添加一个结点与另一个结点相连，但需要保证每个点的相邻结点不超过 4 个（原树已经保证），求最终得到的不同的树的形态的数量。

题目分析

将题目转化一下，如果我们要添加到一个结点到另一个结点 $u$ 上，首先这个点的度数不超过 3。其次我们发现如果我们以 $u$ 为根，若以不同的 $u$ 形成了不同的有根树，那么添加后也一定也是不同的；原来相同的添加后显然也是相同的。所以问题转化为统计不同的以度数不超过 3 的结点为根节点的有根树的数量。

考虑树哈希，第一结点的树哈希值可以 $O(n)$ 算出，而第二个结点的树哈希值显然可以通过换根的方式计算出。

用 $f_u$ 代表以 $u$ 的子树的哈希值 $f_u = \sum_v hashFunc(f_v) + 1$，再用 $g_u$ 代表以 $u$ 为根的哈希值，显然我们可以用 $g_v = f_v + hashFunc(g_u - hashFunc(f_v))$ 来递推。