串（string）是由零個或多個字符組成的有限序列，又名字符串。
字符串有很多函數，replace、ToUpper、ToLower（轉小寫）、Trim（去掉兩邊空格）、IndexOf（從左到右查找子串的位置）、SubString、SubLength等等。
一、串的存儲結構
串的存儲結構與線性表相同，分為順序存儲結構和鏈式存儲結構。
1. 順序存儲結構
串的順序存儲結構是用一組地址連續的存儲單元來存儲串中的字符序列的。按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區。
用“\0”來表示串的終結，不計入串長度，但是計入數組長度。
兩個長度不同的串不可能相等。
2. 鏈式存儲結構
要考慮一個結點是存放一個字符（會造成很大的空間浪費）還是多個字符。除了鏈接串與串的操作有一定方便外，總的來說不如順序存儲量或，性能也不如順序存儲結構好。
二、樸素的模式匹配算法
串的模式匹配：串的定位操作。
時間復雜度：O(1)–最好；O(n+m)–平均；O(n-m+1)*m–最不好
三、KMP模式匹配算法
KMP算法可以大大減少重復遍歷的情況。
next數組（改進樸素匹配）：后面一個與前面一個字符比較，若相等，k值是2，兩個字符k值是3，n個k值相等就是n+1。第一個為0，其他不匹配的情況為1。
nextval數組（改進的KMP匹配）：先計算next數組，逐個字符比較，若相等，nextval[j]=nextval[j]，若不等，推倒重新比較，nextval[j]=next[i]。
三、題目
- n 個字符構成的字符串，假設每個字符都不一樣，問有多少個子串？
n(n+1)/2 + 1 - 設模式串的長度為m,目標串的長度為n,當n≈m且處理只匹配一次的模式時,樸素的匹配(即子串定位函數)算法所花的時間代價可能會更為節省。
