思維導圖
串.png
重點問題
1，什么是串？
2，串的比較，比較的是什么？
3，常用的兩種字符編碼和兩者間的差別？
4，串的存儲結構
5， 關于串的算法
5.1 樸素的算法時間復雜度？（準確復雜度）
5.2 KMP算法時間的核心思想和時間復雜度？
5.3 KMP算法中的next數(shù)組元素的含義及作用？
5.4 KMP算法中的nextval數(shù)組元素的含義及作用？
1，什么是串？
由零個或多個字符組成的有限序列，又叫字符串。
2，串的比較，比較的是什么？
串的比較是通過組成串的字符之間的編碼進行的。
3，常用的兩種字符編碼和兩者間的差別？
為了和ASCII兼容，Uniconde的前256個字符與ASCII完全相同
4，串的存儲結構
- 串的順序存儲結構
用一組地址連續(xù)的存儲單元來存儲串中的字符序列。 - 串的鏈式存儲結構
與線性表的鏈式存儲結構類似。
串結構中的一個結點可以放一個字符也可以放多個字符。
5， 關于串的算法
5.1 樸素的算法時間復雜度？（準確復雜度）
O((n-m+1）* m)
5.2 KMP算法時間的核心思想和時間復雜度？
- 核心思想
比較過的字符串不再比較
1，子串T首個字符與后面的的串任意一個字符都不相等。
2，子串T與主串S的前n為相等。
3，子串T的首字符不可能與主串S的前n為相等。 - 時間復雜度
O(n+m)
5.3 KMP算法中的next數(shù)組元素的含義及作用？
next數(shù)組中元素的含義：已匹配的字符數(shù)前綴和后綴相最大的相同長度 + 1 。
移動位數(shù) = 已匹配的字符數(shù) - 對應的部分匹配值。
5.4 KMP算法中的nextval數(shù)組元素的含義及作用？
可以用next[1]的值去取代它相等的字符后續(xù)next[j]的值。
1，算出next 值。
2，a位字符 的next值，next[a] 位的字符b的next值 比較。
