POJ 1002 - 487-3279(基礎)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1002
題意：略
解法：二叉查找數，map，快排...

POJ 1200 - Crazy Search(基礎)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1200
題意：找出不相同的子串數量，字母表大小和子串長度會給定，這題很推薦hash入門者一做
解法：hash(建議karp-rabin)

POJ 1204 - Word Puzzles(基礎)
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不包括給定模式串的字符串數量。（題意同2778，但不能按2778的方法，建議先做此題，再做2778）
解法：Aho-Corasick自動機 + dp
相關：http://hi.baidu.com/zfy0701/blog/item/c62f41afca8180ca7cd92a19.html

POJ 1743 - Musical Theme(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
題意：找一個串中最長不重疊子串
解法：后綴數組+二分枚舉答案，后綴數組+棧掃描，RK+二分枚舉答案
相關：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 2185 - Milking Grid(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2185
題意：最小矩型的覆蓋
解法：KMP (不多的KMP好題)
相關：http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=33571

POJ 2513 - Colored Sticks(基礎)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2513
題意：轉化成歐拉回路
解法：并查集+hash，并查集+Trie

POJ 2774 - Long Long Message(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2774
題意：找兩個串的公共最長子串
解法：后綴數組，Oracle Factor自動機，后綴自動機
相關：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不包括給定模式串的字符串數量。
解法：Aho-Corasick自動機(前綴樹) + 矩陣快速乘法
相關：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html
類似于1625，建議先做1625

POJ 1699 - Best Sequence(基礎)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1699
題意：轉換為TSP問題（注意子串的包含關系?。?br>解法：回溯，狀態dp

POJ 3376 - Finding Palindromes(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3376
題意：找回文串組合
解法：找出規律，然后Trie + kmp推廣形式

POJ 3415 - Common Substrings(較難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3415
題意：統計兩個串中長度>=k的公共子串的數量
解法：后綴數組+棧掃描，后綴自動機
相關：http://hi.baidu.com/zfy0701/blog/item/f2278a0928991dca3bc763a0.html

POJ 3080 - Blue Jeans(如果用暴力，就很簡單)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3080
題意：求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
題意：求一個串中重復出現至少k次的最長子串
解法：后綴數組+棧掃描，hash + 二分

POJ 3294 - Life Forms(較難，強烈推薦)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3294
題意：n個串中，為大于n/2個串所共有的所有最長子串
解法：后綴數組+棧掃描，暴力(很容易被卡掉)，后綴數組+線段樹(?)
相關：http://hi.baidu.com/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html

POJ 3576 - Language Recognition(中等)

[耗子寫過]

題意：給定一些單詞,讓你用一個狀態數最小的DFA表示這些單詞,求最小的狀態數.
解法 : 這里不用去套編譯書上的子集劃分的方法,由于這個DFA一定沒有環, 所以合并兩個集合,實際上是判兩個子樹是否相等,注意終態和非終態的判斷.hash判有多少棵不相同的樹即可,

數據和標程:鏈

POJ 3581 - Sequence(中等)

題意：把原串分三段并反轉，求字典序最小的那串
解法：

POJ 3630 - Phone List(基礎，強烈推薦用此題練Trie)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3630
題意：給n個串，看是否有一個串是另一個串的前綴
解法：快排，Trie

POJ 3690 - Constellations(基礎)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3690
題意：二維串匹配
解法：轉換為一維，或者用多串匹配

POJ 3691 - DNA repair(中等)

[耗子讀過]

題意:給你一些有害的DNA片斷(長度<20, 數量<50),和一個DNA序列,對該序列進行最少的修改,使之不包含任何有害片斷.一次修改只能是替換一個字符

解法:建造一個ac自動機,開始dp,用滾動數組轉移,狀態表示到達當前狀態并且沒有有害片斷所需的最小修改量.

POJ 3693 - Maximum repetition substring(難)

[耗子讀過]
題意：求最循環節最多的子串
解法：09年論文上的例題,后綴數組

zyf0701說:我所知道的最好的做法應該是先做s-factorization(也就是lempel-ziv)，然后在分解之后的每一段中枚舉周期，周期可以通過推導關系式確定是否合法，然后可確定循環次數，取最大的，中間還用到了對kmp的擴展。具體來說有KK算法，和ML算法兩種，其中ML不能遍歷所有的runs。

其他OJ：

SPOJ 2743 - Prefix Tiling

[耗子讀過]

題意:對于每個前綴x定義 L(x) = x的連續重復串在原串上能覆蓋的最長距離,起點固定. 求L(1)+L(2)+...+L(N)的值.

解法:先求出所有后綴與原串的最長公共前綴.然后枚舉x,每次倍增的跳躍,時間nlogn

空罐 Cans
[耗子讀過]

題意：描述很長,自己看吧
解法：建好ac自動機,然后開始dp

HDOJ 2471 - History of Languages(杭州現場賽)

[耗子讀過]

題意:給兩個DFA,判斷他們是否相等.要求復雜度至少O(n^2)

神奇的解法令人膜拜: 鏈

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