题单一放出来，各路神仙各显神通，\(\text{SAM}\) 大神怒切的同时大喊这不都是板题？AC自动机大神大喊他不会 \(\text{KMP}\)？Z函数大神大叫这是板题？
而我，发现字符串算法是我忘得最干净的一块，只记得无脑 \(\text{Hash}\)。一怒之下，重学了 \(\text{SAM}\)。
CF432D Prefixes and Suffixes
统计每个字串出现的次数，这不 \(\text{SAM}\) 板题。问题在于怎么判断一个串是否既是前缀又是后缀。这个东西 \(\text{KMP}\) 显然能做，但都有 \(\text{SAM}\) 了，最方便的方法是在 \(\text{SAM}\) 上查前缀的同时，用 \(\text{Hash}\) 判一下是否为后缀，也可以将整串所在节点到根的整条后缀链上的节点（每个节点代表的状态里子串的集合即为所有后缀组成的集合）打上标记。
P2852 [USACO06DEC] Milk Patterns G
最喜欢的无脑 \(\text{Hash}\)，二分最长的长度，\(\text{Hash}\) 判断是否存在出现次数至少为 \(K\) 次的串。
时间复杂度 \(O(n \log n)\)
标签：Hash,SAM,板题,后缀,text,7.20,大神,字符串 From： https://www.cnblogs.com/Semorius/p/17572871.html