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入門者一做
解法：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ī)(前綴樹) + 矩陣快速乘法
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
類似于1625，建議先做1625

POJ 1699 - Best Sequence(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1699
題意：轉(zhuǎn)換為TSP問(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ù)組+線段樹(?)
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html

POJ 3576 - Language Recognition(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3576
題意：求一個(gè)dfa，它滿足兩個(gè)條件，1、能識(shí)別所有詞的dfa，2、要求狀態(tài)數(shù)最少。
解法：trie + hash
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/b8332b5cd90e7b45fbf2c033.html

POJ 3581 - Sequence(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3581
題意：把原串分三段并反轉(zhuǎn)，求字典序最小的那串
解法：后綴數(shù)組
本來(lái)覺(jué)得很水，但卻是我目前做得最失敗的一道后綴數(shù)組題

 

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(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3691
題意：修復(fù)非法字符串需要替換的最少字符數(shù)
解法：動(dòng)態(tài)規(guī)劃，如果使用AC自動(dòng)機(jī)去做dp的話比較簡(jiǎn)單且只需要二維，用dp[i][j]表示第i個(gè)字符時(shí)，第j種狀態(tài)(不是非法狀態(tài))所需要最小的修改量

POJ 3693 - Maximum repetition substring(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3693
題意：求最循環(huán)節(jié)最多的子串
解法：我所知道的最好的做法應(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
http://www.spoj.pl/problems/PRETILE/
找規(guī)律

空罐 Cans(這個(gè)自動(dòng)機(jī)dp還是有意思的)
http://cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=b179

HDOJ 2471 - History of Languages(杭州現(xiàn)場(chǎng)賽)
http://acm.hdu.edu.cn/showproblem.php?pid=2471
自動(dòng)機(jī)的等價(jià)性，劃分集合的dp

HDU 2967 - Morphing is fun
http://acm.hdu.edu.cn/showproblem.php?pid=2967
UVA上也過(guò)得人比較少的一道題，需要分情況討論幾種情況