KMP【整理】

学习资料

【KMP】Matrix67：http://www.matrix67.com/blog/archives/115

【拓展KMP】刘雅琼ppt：http://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html

【浅析“最小表示法”思想在字符串循环同构问题中的应用--03 周源】：1.论文 2.ppt

kmp暂时告一段落，做了刚好一个星期，收集的各种Google加Baidu刨出来的KMP题目。还有两题目前还没想法，说不定哪天突然灵感来了再补上。

HDU 1711Number Sequence 模板题

HDU 1686 Oulipo 模板题

HDU 2087剪花布条 KMP模板题，也可直接用strstr暴力

HDU 3068 最长回文

HDU 4300Clairewd’s message 拓展KMP， 这题用暴力（不用任何算法）也可水过

HDU 2594 Simpsons’ Hidden Talents 用KMP寻找s2中的s1串，最后一个状态值j表示的就是最长的s2的后缀与s1的前缀。

HDU 3746Cyclic Nacklace 最短循环节（字符串后面添加x个字符，让x最小，使其由某个前缀子串至少循环2次构成的）

HDU 1358 Period 最短循环节

HDU 2203 亲和串 循环移位相当于把数组扩大成两倍，再KMP匹配

HDU 3613Best Reward 拓展KMP求前缀回文

HDU 3374String Problem 最小最大表示法+KMP
HDU 3336 Count the string 经典， KMP+DP

HDU 4333 Revolving Digits 拓展KMP

HUST 1010The Minimum Length 转换成求最短循环节

HUST 1328String 同HDU3336

XDU 1154 大黄的选票 找到前缀位置，用dp[i]表示i之前有多少个前缀，然后再找后缀。注意前缀的开头一定要在后缀之前。

FZU 1901 Period II KMP或拓展KMP

CF149E Martian Strings 先找到匹配串前缀在原串中最左边的位置，然后找后缀的位置是否在这个位置之后。

CF182D Common Divisors 最短循环节，循环节周期

CF 126B Password Next数组

poj 1226 Substrings 水。同poj3080
poj 2185Milking Grid
poj 2406Power Strings 最短循环节
poj 2541Binary Witch 逆序转换原字符串，变成求最长公共前缀（即使这样也是数据太水才过的，正解是状态压缩dp）

poj 2752Seek the Name, Seek the Fame 理解失配函数！

poj 3080Blue Jeans 枚举所有子串，看能否全部序列都匹配

poj 3450 Corporate Identity 同poj 3080

poj 3167 Cow Patterns

poj 3461Oulipo 同hdu 1686

zoj 3587Marlon's String 拓展KMP+dp

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)