NOIP2024集训Day58 字符串

NOIP2024集训Day58 字符串

C. [CEOI2011] Matching

发现要做的是排名串的匹配。

考虑把它转成这个位置之前有多少个数小于当前这个数，这样就只要每个位置都对应相等的，那就一定是合法的。

然后就可以类似 KMP 的预处理出一个 \(nxt\) 数组，然后再类似 KMP 的匹配。

因为需要支持动态求前面一段区间有多少个数比这个数小，所以需要用树状数组维护。

E. [POI2005] SZA-Template

有个结论，一个字符串的印章一定是它的 border，因为只有这样才可能兼顾首尾，但是反过来就不行，也就是说一个字符串的 border \(\ne\) 一个字符串的印章。

设 \(f_i\) 表示前 \(i\) 个字符串的最小印章长度。

\(f_i\) 的取值只有可能是 \(i\) 和 \(f_{nxt_i}\)，\(i\) 就是取自己为印章，\(f_{nxt_i}\) 表示先将它的 border 想办法填出来，再在末尾加上剩余字符。

什么时候能从 \(f_{nxt_i}\) 转移过来？

先找到一个最大的 \(f_j = f_{nxt_i}\)，由于在 \(j\) 后面我们至多填上 \(f_{nxt_i}\) 长度的字符串，所以当 \(i - j \le f_{nxt_i}\) 时，可以转移。

对于一个合法的 \(j\)，维护一个 dp 值对应的最大下标即可。