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ù)量，字母表大小和子串長度會給定，這題很推薦hash入門者一做
解法：hash(建議karp-rabin)

POJ 1204 - Word Puzzles(基礎(chǔ))
http://acm.pku.edu.cn/JudgeOnline/problem?id=1204
題意：基本多串匹配
解法：多串匹配自動機（單串去弄肯定會超時）

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
題意：求長度為n不包括給定模式串的字符串?dāng)?shù)量。（題意同2778，但不能按2778的方法，建議先做此題，再做2778）
解法：Aho-Corasick自動機 + 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
題意：找一個串中最長不重疊子串
解法：后綴數(shù)組+二分枚舉答案，后綴數(shù)組+棧掃描，RK+二分枚舉答案
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 1816 - Wild Words(中等，絕對的Trie應(yīng)用好題，同時又是搜索好題)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1816
題意：擴展多串模式匹配(含?, *)
解法：Trie + dfs，有興趣也可用基于位并行的自動機(可參考柔性字符串匹配，擴展匹配章節(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
題意：找兩個串的公共最長子串
解法：后綴數(shù)組，Oracle Factor自動機，后綴自動機
相關(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
題意：求長度為n不包括給定模式串的字符串?dāng)?shù)量。
解法：Aho-Corasick自動機(前綴樹) + 矩陣快速乘法
相關(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問題（注意子串的包含關(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)計兩個串中長度>=k的公共子串的數(shù)量
解法：后綴數(shù)組+棧掃描，后綴自動機
相關(guān)：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 3080 - Blue Jeans(如果用暴力，就很簡單)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3080
題意：求n個串的最長公共子串
解法：后綴數(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
題意：略
解法：有意思的自動機dp

POJ 3261 - Milk Patterns(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3261
題意：求一個串中重復(fù)出現(xiàn)至少k次的最長子串
解法：后綴數(shù)組+棧掃描，hash + 二分

POJ 3294 - Life Forms(較難，強烈推薦)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3294
題意：n個串中，為大于n/2個串所共有的所有最長子串
解法：后綴數(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
題意：求一個dfa，它滿足兩個條件，1、能識別所有詞的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ù)組
本來覺得很水，但卻是我目前做得最失敗的一道后綴數(shù)組題

 

POJ 3630 - Phone List(基礎(chǔ)，強烈推薦用此題練Trie)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3630
題意：給n個串，看是否有一個串是另一個串的前綴
解法：快排，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ù)
解法：動態(tài)規(guī)劃，如果使用AC自動機去做dp的話比較簡單且只需要二維，用dp[i][j]表示第i個字符時，第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)，然后在分解之后的每一段中枚舉周期，周期可以通過推導(dǎo)關(guān)系式確定是否合法，然后可確定循環(huán)次數(shù)，取最大的，中間還用到了對kmp的擴展。具體來說有KK算法，和ML算法兩種，其中ML不能遍歷所有的runs。

其他OJ：

SPOJ 2743 - Prefix Tiling
http://www.spoj.pl/problems/PRETILE/
找規(guī)律

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

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

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