总结

今天是冬月廿九，明天就腊月了哦。今天是字符串专题！

看到一篇通俗易懂的博客！强烈推荐！基础字符串 学习笔记 。

P5829 【模板】失配树

自豪地使用 border 引理来做这道题！

[WC2016] 论战捆竹竿

喵喵题。一眼同余，然后发现等差然后单调队列更新就行。这道题 UOJ 上我要卡常，好可恶。讲一讲有一个数据的构造方式，被我和 UKER 盒出来啦哈哈哈。就是长度，然后前个字符是每一位字符是编号的 ctz + 'a'，然后中间是一些字符 r，然后结尾是个和前个一样的字符串。

6624. String Problem

KMP 的做法很有趣，讲一讲。这道题是什么呢？就是一个长的字符串，然后让你求每个前缀的最大子串输出左右编号，那么显然当前前缀的一个后缀。那么添加一个字符，新的最大子串一定是原来这个最大子串的一个 border 加上新的字符，容易证明。要找到的相当于一个最短的前缀 border 使得它的下一位比新加的小，那么最后接上新字符的字符串就是这个 border。容易发现我们的 nxt 相当于把 border 从小到大，然后后一个字符如果变大了这个 border 一定没有共贡献，然后剩下的 border 的后一个字符一定是递减的，顺着来就是递增的，然后暴力跳就可以。然后考虑新的 nxt。由于前面的构建方法，只有当前一个 nxt 的下一个刚好是新字符时 nxt 才不是 0。否则一定是没有任何 border 的。

后记

今天做的题好少，他们有人做的题好多。就当我很笨吧……感觉怪怪的。不能这么说。好歹今天还是做了一道黑题的。嘿嘿。这里要警示后人了。开局部对象最好开在其适用的生命周期范围内，不然容易忘记清空之类的。循环的话就开在循环内。好耶！ヽ(✿ﾟ▽ﾟ)ノ