今天的题目没有那么难，挑一些不蛮板的题目来讲。建议不要光看，打个草稿画一下图，这个是解字符串题的关键。

[POI2005] SZA-Template

题目描述

你打算在纸上印一串字母。

为了完成这项工作，你决定刻一个印章。印章每使用一次，就会将印章上的所有字母印到纸上。

同一个位置的相同字符可以印多次。例如：用 aba 这个印章可以完成印制 ababa 的工作（中间的 a 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 aba 这个印章不可以完成印制 abcba 的工作。

因为刻印章是一个不太容易的工作，你希望印章的字符串长度尽可能小。

思路点拨

本题具体有两种做法，失配树和动态规划。这里讲述更好理解的失配树做法，想要了解动态规划做法可以自己口胡...

我们考虑建出失配树，然后寻找一些性质。对于一个印章，我们肯定需要在 \(1\) 开头的位置印刷一次，在 \(n\) 结尾的地方印刷一次，那么这个印章是 \(1,2,...,n-1,n\) 的一个 \(\text{border}\) 。答案返回到失配树上，就是根节点到 \(n\) 的这一条路径上。我们的答案是在这条路径上合法，并且深度最小的点。

我们接着想，一个答案什么时候合法？对于一个失配树上的节点 \(u\) ，我们对其子树内的节点排序。如果存在排序后两个相邻的元素 \(i,j\) 有 \(\text{abs(i-j)}>u\) ，那么这个 \(u\) 肯定不合法。具体大家可以结合失配树的意义自行理解一下。类似于出现了一个长度大于 \(u\) 的区间无法被 \(1\) 到 \(u\) 这个 \(\text{border}\) 印刷出来。我们现在需要解决的就是如何找到这个最大的邻值。

如果我们从 \(n\) 一路走到根节点，这个最大的邻值是单调不递增的，我们不好维护。但是如果我们是从根节点走到 \(n\) ，那么添加节点机会变成添加节点，这个最大邻值也就是单调不递减的。我们可以使用一个双向链表每次 \(O(1)\) 维护。总体时间复杂度 \(O(n)\) 。

\(\text{hdu3336}\)

题目描述

给出一个字符串 \(s\) ，求 \(s\) 的每一个前缀在字符串中出现次数之和。

\(n \leqslant 10^6\) 。

思路点拨

考虑建立失配树。对于一个前缀而言，它出现的次数就是它所对应节点的子树大小，简单统计一下就可以了。

时间复杂度 \(O(n)\) 。

\(\text{Luogu3435}\)

题目描述

对于一个仅含小写字母的字符串 \(a\)，\(p\) 为 \(a\) 的前缀且 \(p\ne a\)，那么我们称 \(p\) 为 \(a\) 的 proper 前缀。

规定字符串 \(Q\) 表示 \(a\) 的周期，当且仅当 \(Q\) 是 \(a\) 的 proper 前缀且 \(a\) 是 \(Q+Q\) 的前缀。若这样的字符串不存在，则 \(a\) 的周期为空串。

例如 ab 是 abab 的一个周期，因为 ab 是 abab 的 proper 前缀，且 abab 是 ab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

\(n \leqslant 10^6\) 。

思路点拨

考虑一个前缀的最大周期到底是什么，就是这个前缀的长度减去这个前缀的最小 \(\text{border}\) ，还算是好推。但凡是你拿起笔打了草稿就会知道。

求出最小的 \(\text{border}\) 可以使用动态规划，对于 \(i\) 前缀而言（\(\text{fail}\) 为失配数组）：

• 不存在 \(fail_i\)，\(dp_i=i\) 。

• 存在 \(fail_i\) 但是不存在 \(fail_{fail_i}\) ，\(dp_i=fail_i\) 。

• 存在 \(fail_i\) 并且存在 \(fail_{fail_i}\) ，\(dp_i=dp_{fail_i}\) 。

答案就是 \(\sum i-dp_i\) ，时间复杂度 \(O(n)\) 。

\(\text{Luogu7456}\)

题目描述

现在给出了一个字符串 \(c\) 以及 \(n\) 个字符串 \(s\) 。

你需要挑选出 \(n\) 个字符串中的一些（可以多次选同一个字符串）拼出字符串 \(c\) 。拼的时候两个字符串可以重叠，但是重叠的部分必须相同。

你需要选出的字符串数量尽可能少。

\(n ,|c| ,\sum |s| \leqslant 3\times 10^5\) 。

思路点拨

如果我已经拼好了 \(c\) 的前 \(i\) 个字符，那么我下一个字符会选那个？其实答案只有一个，就是可以让这个已经拼凑出来的字符串尽可能变长的那一个。

那么对于一个 \(c\) 的前缀 \(c_1,..,c_i\) ，它又可以从哪里来？我们找到以 \(i\) 为结尾的最长的 \(n\) 个字符串中的字符串，假设其长度为 \(len\) 。那么对于前缀 \(j \in [i-len,i-1]\) ，都可以通过添加这个字符串扩展到 \(i\) 。

我们定义状态 \(dp_i\) 表示目前填完 \(c_1,...,c_i\) 的最少字符串数量。转移比较简单，假设以 \(i\) 结尾的最长字符串长度为 \(len_i\) （这个可以使用 \(\text{ACAM}\) 求 \(fail\) 树的链上最大值求出），那么

这个可以使用线段树优化。时间复杂度 \(O((|c|+\sum |s| )\log |c|)\) 。‘

\(\text{Luogu3546}\)

题目描述

对于两个串 \(S_1, S_2\)，如果能够将 \(S_1\) 的一个后缀移动到开头后变成 \(S_2\)，就称 \(S_1\) 和 \(S_2\) 循环相同。例如串 ababba 和串 abbaab 是循环相同的。

给出一个长度为 \(n\) 的串 \(S\)，求满足下面条件的最大的 \(L(L\leq \frac n 2)\)：\(S\) 的 \(L\) 前缀和 \(S\) 的 \(L\) 后缀是循环相同的。

• 对于 \(100\%\) 数据，保证 \(1\le n\le 10^6\)。

思路点拨

我们看到第一句话：对于两个串 \(S_1, S_2\)，如果能够将 \(S_1\) 的一个后缀移动到开头后变成 \(S_2\)，就称 \(S_1\) 和 \(S_2\) 循环相同。我们想一下 \(s1,s2\) 会是什么形式？\(s1=AB,s2=BA\) ， \(A,B\) 均是一个字符串。这个很好理解，\(B\) 就是我要从 \(s1\) 的后边循环到前边的字符串。

又因为我们需要寻找的 \(s1,s2\) 都是前后缀，所以 \(A\) 部分就应当是原字符串的一个 \(\text{border}\) 。\(B\) 部分就是原字符串去除 \(A\) 这个前后缀之后的最长 \(\text{border}\) 。我们考虑枚举 \(A\) ,快速计算 \(B\) ，因为 \(B\) 是一个最大值。

简单画一下图就会发现一个小结论。我们假设去除前后缀 \(i\) 的字符串的最长 \(\text{border}\) 为 \(dp_i\) ，那么 \(dp_{i} \leqslant dp_{i+1}+2\) 。不然 \(dp_{i+1}\) 的长度完全可以更长，算了，挂张图吧（手动latex，草稿本上随便改了一下，将就看吧）：

所以我们可以在 \(O(n)\) 的时间算出 \(dp\) 数组（用哈希判断相同）。枚举 \(A\) 不是时间瓶颈。

总时间复杂度 \(O(n)\) 。