POJ 1002 - 487-3279(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1002
題意：略
解法：二叉查找數(shù)，map，快排...
POJ 1200 - Crazy Search(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1200
題意：找出不相同的子串?dāng)?shù)量，字母表大小和子串長(zhǎng)度會(huì)給定，這題很推薦hash入門(mén)者一做
解法：hash(建議karp-rabin)
POJ 1204 - Word Puzzles(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1204
題意：基本多串匹配
解法：多串匹配自動(dòng)機(jī)（單串去弄肯定會(huì)超時(shí)）
POJ 1229 - Wild Domains(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1229
題意：模糊匹配
解法：dp
POJ 1625 - Censored!(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1625
題意：求長(zhǎng)度為n不包括給定模式串的字符串?dāng)?shù)量。（題意同2778，但不能按2778的方法，建議先做此題，再做2778）
解法：Aho-Corasick自動(dòng)機(jī) + dp
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/c62f41afca8180ca7cd92a19.html
POJ 1743 - Musical Theme(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
題意：找一個(gè)串中最長(zhǎng)不重疊子串
解法：后綴數(shù)組+二分枚舉答案，后綴數(shù)組+棧掃描，RK+二分枚舉答案
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
POJ 1816 - Wild Words(中等，絕對(duì)的Trie應(yīng)用好題，同時(shí)又是搜索好題)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1816題意：擴(kuò)展多串模式匹配(含?, *)
解法：Trie + dfs，有興趣也可用基于位并行的自動(dòng)機(jī)(可參考柔性字符串匹配，擴(kuò)展匹配章節(jié))
POJ 2185 - Milking Grid(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2185
題意：最小矩型的覆蓋
解法：KMP (不多的KMP好題)
相關(guān)：http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=33571
POJ 2513 - Colored Sticks(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=2513
題意：轉(zhuǎn)化成歐拉回路
解法：并查集+hash，并查集+Trie
POJ 2774 - Long Long Message(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2774
題意：找兩個(gè)串的公共最長(zhǎng)子串
解法：后綴數(shù)組，Oracle Factor自動(dòng)機(jī)，后綴自動(dòng)機(jī)
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
http://hi.baidu.com/zfy0701/blog/item/d9fedbd14581113d9b5027ab.html
POJ 2778 - DNA Sequence(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2778
題意：求長(zhǎng)度為n不包括給定模式串的字符串?dāng)?shù)量。
解法：Aho-Corasick自動(dòng)機(jī)(前綴樹(shù)) + 矩陣快速乘法
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
類(lèi)似于1625，建議先做1625
POJ 1699 - Best Sequence(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1699
題意：轉(zhuǎn)換為T(mén)SP問(wèn)題（注意子串的包含關(guān)系！）
解法：回溯，狀態(tài)dp
POJ 3376 - Finding Palindromes(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3376
題意：找回文串組合
解法：找出規(guī)律，然后Trie + kmp推廣形式
POJ 3415 - Common Substrings(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3415
題意：統(tǒng)計(jì)兩個(gè)串中長(zhǎng)度>=k的公共子串的數(shù)量
解法：后綴數(shù)組+棧掃描，后綴自動(dòng)機(jī)
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
POJ 3080 - Blue Jeans(如果用暴力，就很簡(jiǎn)單)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3080
題意：求n個(gè)串的最長(zhǎng)公共子串
解法：后綴數(shù)組+棧掃描，后綴數(shù)組+二分枚舉，暴力
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html
POJ 3208 - Apocalypse Someday(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3208
題意：略
解法：有意思的自動(dòng)機(jī)dp
POJ 3261 - Milk Patterns(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3261
題意：求一個(gè)串中重復(fù)出現(xiàn)至少k次的最長(zhǎng)子串
解法：后綴數(shù)組+棧掃描，hash + 二分
POJ 3294 - Life Forms(較難，強(qiáng)烈推薦)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3294
題意：n個(gè)串中，為大于n/2個(gè)串所共有的所有最長(zhǎng)子串
解法：后綴數(shù)組+棧掃描，暴力(很容易被卡掉)，后綴數(shù)組+線(xiàn)段樹(shù)(?)
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html
POJ 3576 - Language Recognition(中等)
[耗子寫(xiě)過(guò)]
題意：給定一些單詞,讓你用一個(gè)狀態(tài)數(shù)最小的DFA表示這些單詞,求最小的狀態(tài)數(shù).
解法 : 這里不用去套編譯書(shū)上的子集劃分的方法,由于這個(gè)DFA一定沒(méi)有環(huán), 所以合并兩個(gè)集合,實(shí)際上是判兩個(gè)子樹(shù)是否相等,注意終態(tài)和非終態(tài)的判斷.hash判有多少棵不相同的樹(shù)即可,
數(shù)據(jù)和標(biāo)程:鏈
POJ 3581 - Sequence(中等)
題意：把原串分三段并反轉(zhuǎn)，求字典序最小的那串
解法：
POJ 3630 - Phone List(基礎(chǔ)，強(qiáng)烈推薦用此題練Trie)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3630
題意：給n個(gè)串，看是否有一個(gè)串是另一個(gè)串的前綴
解法：快排，Trie
POJ 3690 - Constellations(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=3690
題意：二維串匹配
解法：轉(zhuǎn)換為一維，或者用多串匹配
POJ 3691 - DNA repair(中等)
[耗子讀過(guò)]
題意:給你一些有害的DNA片斷(長(zhǎng)度<20, 數(shù)量<50),和一個(gè)DNA序列,對(duì)該序列進(jìn)行最少的修改,使之不包含任何有害片斷.一次修改只能是替換一個(gè)字符
解法:建造一個(gè)ac自動(dòng)機(jī),開(kāi)始dp,用滾動(dòng)數(shù)組轉(zhuǎn)移,狀態(tài)表示到達(dá)當(dāng)前狀態(tài)并且沒(méi)有有害片斷所需的最小修改量.
POJ 3693 - Maximum repetition substring(難)
[耗子讀過(guò)]
題意：求最循環(huán)節(jié)最多的子串
解法：09年論文上的例題,后綴數(shù)組
zyf0701說(shuō):我所知道的最好的做法應(yīng)該是先做s-factorization(也就是lempel-ziv)，然后在分解之后的每一段中枚舉周期，周期可以通過(guò)推導(dǎo)關(guān)系式確定是否合法，然后可確定循環(huán)次數(shù)，取最大的，中間還用到了對(duì)kmp的擴(kuò)展。具體來(lái)說(shuō)有KK算法，和ML算法兩種，其中ML不能遍歷所有的runs。
其他OJ：
SPOJ 2743 - Prefix Tiling
[耗子讀過(guò)]
題意:對(duì)于每個(gè)前綴x定義 L(x) = x的連續(xù)重復(fù)串在原串上能覆蓋的最長(zhǎng)距離,起點(diǎn)固定. 求L(1)+L(2)+...+L(N)的值.
解法:先求出所有后綴與原串的最長(zhǎng)公共前綴.然后枚舉x,每次倍增的跳躍,時(shí)間nlogn
空罐 Cans
[耗子讀過(guò)]
題意：描述很長(zhǎng),自己看吧
解法：建好ac自動(dòng)機(jī),然后開(kāi)始dp
HDOJ 2471 - History of Languages(杭州現(xiàn)場(chǎng)賽)
[耗子讀過(guò)]
題意:給兩個(gè)DFA,判斷他們是否相等.要求復(fù)雜度至少O(n^2)
神奇的解法令人膜拜: 鏈
HDU 2967 - Morphing is fun
http://acm.hdu.edu.cn/showproblem.php?pid=2967
UVA上也過(guò)得人比較少的一道題，需要分情況討論幾種情況，我09年過(guò)的最得意的題