KMP和KMP是好朋友

正文索引 [隐藏]

BZOJ 1251: 序列终结者

splay模板题,再写一遍找手感!Wa了一次!splay对无用节点的处理真的很重要!(其实是你自己偷懒没有判断到底存不存在子节点吧!

HDU 5147 Sequence II

树状数组!枚举C,顺带统计C前的二元组(A,B),树状数组求(C,D)个数。

HDU 5145 NPY and girls

区间L,R的答案=(R – L -1)! / (II 每个相同数字个数的阶乘)
莫队直接推!

————————————————密封线以下是正文———————————–

POJ 3461 Oulipo

KMP匹配个数

POJ 2752 Seek the Name, Seek the Fame

寻找子串即是前缀又是后缀
Ans->nxt[Ans] 依次寻找答案

POJ 2406 Power Strings

寻找串的最大循环子串
len-nxt[len]为串的最小循环节

POJ 1961 Period

寻找每个子串的最短循环节长度(如果有的话)
枚举子串,然后同上

HDU 3336 Count the string

求子串是其本身前缀的个数->DP

HDU 3746 Cyclic Nacklace

补偿多少个字符成为循环

HDU 2087 剪花布条

匹配完成重置的KMP

HDU 2594 Simpsons’ Hidden Talents

最长第一个串的前缀的二个的后缀
拼起来KMP

HDU 4763 Theme Section

同上一题,Ans->nxt[Ans]枚举长度,验证中间是否有符合Ans=nxt[i]