前言
- 本文主要講解 數(shù)據(jù)結(jié)構(gòu)中的串
- 內(nèi)容包括其特點(diǎn)、結(jié)構(gòu)等，希望你們會(huì)喜歡。
目錄
示意圖
1. 簡(jiǎn)介
示意圖
2. 存儲(chǔ)結(jié)構(gòu)介紹
包括：順序存儲(chǔ)結(jié)構(gòu) & 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
示意圖
3. 串的比較
示意圖
4. 子串的定位
- 子串定位 的主要任務(wù)是：確定主串是否存在子串 & 子串在主串中的位置
子串的定位操作 也稱 串的模式匹配
- 下面主要講解串模式匹配的重要方法：
KMP模式匹配算法
4.1 KMP模式匹配算法 簡(jiǎn)介
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
示意圖
4.2 具體算法
- 概念：字符串的前綴 & 后綴
示意圖
- 具體使用
步驟1：計(jì)算出子串（T串）各個(gè)位置的j值的變化
步驟2：根據(jù)步驟1計(jì)算出的next數(shù)組，將子串與主串進(jìn)行模式匹配
示意圖
下面將重點(diǎn)講解步驟1：計(jì)算出子串（T串）各個(gè)位置的 j 值的變化
- 定義1數(shù)組：
next [ j ]= 子串（T串）各個(gè)位置的j值的變化
j值僅取決于：T串 當(dāng)前字符 前后綴字符的相似度
-
next [ j ]值的函數(shù)定義如下
示意圖 舉例說(shuō)明
示意圖
4.3 算法改進(jìn)
示意圖
5. 總結(jié)
- 本文主要講解了 數(shù)據(jù)結(jié)構(gòu)中 串的知識(shí)，含 其特點(diǎn)、結(jié)構(gòu)等
- 下面我將繼續(xù)對(duì) 數(shù)據(jù)結(jié)構(gòu)進(jìn)行講解，有興趣可以繼續(xù)關(guān)注Carson_Ho的簡(jiǎn)書
歡迎關(guān)注Carson_Ho的簡(jiǎn)書！
不定期分享關(guān)于安卓開發(fā)的干貨，追求短、平、快，但卻不缺深度。
請(qǐng)點(diǎn)贊！因?yàn)槟愕墓膭?lì)是我寫作的最大動(dòng)力！
相關(guān)文章閱讀
Android開發(fā)：最全面、最易懂的Android屏幕適配解決方案
Android事件分發(fā)機(jī)制詳解：史上最全面、最易懂
Android開發(fā)：史上最全的Android消息推送解決方案
Android開發(fā)：最全面、最易懂的Webview詳解
Android開發(fā)：JSON簡(jiǎn)介及最全面解析方法!
Android四大組件：BroadcastReceiver史上最全面解析
Android四大組件：Service服務(wù)史上最全面解析
