串是由零個或多個字符組成的有限序列，又名叫字符串；零個字符的串稱為空串(null string，也用Φ表示)，只包含空格的串稱為空格串，串中的子序列稱作子串
串的比較：以ASCII碼為字符集；比較對應(yīng)位置的值和長短
存儲結(jié)構(gòu)
順序存儲結(jié)構(gòu)：用普通方式實現(xiàn)會產(chǎn)生很多問題，因此要做變化：串值的存儲空間可在程序執(zhí)行過程中動態(tài)分配而得
鏈?zhǔn)酱鎯Y(jié)構(gòu)：一個結(jié)點可以存放一個或多個字符，若末尾結(jié)點未滿則用"#"或其他非串值字符補全
- 串的鏈?zhǔn)酱鎯υ谶B接串與串操作時有一定方便，但總的來說不如順序存儲靈活，性能也沒它好
樸素的模式匹配算法
子串的定位操作通常稱作串的模式匹配
思路：對主串的每一個字符作為子串開頭，與要求匹配的字符串進行匹配，對主串做大循環(huán)(循環(huán)回溯主串下標(biāo))，每個主串字符開頭做子串長度的小循環(huán)，直到循環(huán)結(jié)束
時間復(fù)雜度：
- 最好：O(1)
- 平均：O(n+m)
- 最壞：O((n-m+1)*m)
KMP模式匹配算法
樸素的模式匹配算法很低效，所以有了一個模式匹配算法可以避免重復(fù)遍歷的情況，我們把他稱為克努特—莫里斯—普拉特算法，簡稱KMP算法
- 原理：不讓沒必要的回溯發(fā)生，檢查子串的結(jié)構(gòu)中是否有重復(fù)，若重復(fù)可以省略一部分不必要的判斷步驟；根據(jù)前后綴相似度來決定匹配操作
- 把子串各位置的j值(即下標(biāo))的變化定義為一個數(shù)組next，數(shù)組的長度就是子串的長度，由此可得：
next[j] = 0，當(dāng)j=1時
= Max{ k| 1<k<j，且'P1···Pk-1'='Pj-k+1···Pj-1' } 當(dāng)此集合不空時 # 此行P后面的數(shù)字及kj都是下標(biāo)
= 1，其他情況
推導(dǎo)：T(子串)='abcabx'
當(dāng)j=1時，next[1]=0;
當(dāng)j=2時，j由1到j(luò)-1只有字符'a', next[2]=1; # 屬于其他情況
當(dāng)j=3時，'ab', next[3]=1;
當(dāng)j=4時，'abc', next[4]=1;
當(dāng)j=5時，'abca', 可推算出k為2(P1=P4), 因此next[5]=2;
當(dāng)j=6時，'abcabx', next[6]=3;
結(jié)果即next[j] = 011123
如果前后綴一個字符相等, k值是2, 兩個字符k值是3, 前后綴n個字符相等k值就是n+1
- 思路：得到子串的next數(shù)組；限定條件使下標(biāo)在長度范圍內(nèi)進行循環(huán)；比較子串(下標(biāo)j)和主串(下標(biāo)i)字符，相等就繼續(xù)(且滿足j=0)，否則j退回合適的位置(i是不變的)；最后返回位置或0(即不存在)
- 與樸素匹配算法比較：去掉了i值回溯的部分；使得子串循環(huán)部分的大O由O(m)變?yōu)镺(n)(m為子串長，n為主串長)，因此整個算法的時間復(fù)雜度為O(n+m)，但KMP與樸素匹配差異并不明顯，除非是模式與主串之間存在許多"部分匹配"時
- KMP算法的改進(數(shù)組nextval)：計算出next值的同時，如果a位字符與它next值指向的b位字符相等，則該a位的nextval就指向b位的nextval值，如果不等，則該a位的nextval值就是它自己a位的next的值
