串

---

目錄

串

一、串：

二、串的存儲結構：

三、模式匹配

1.簡單模式匹配（BF算法）

2.KMP算法

2.1-next（j）數組手工求解

2.2-nextval（j）數組手工求解

---

---

一、串：

內容受限的線性表，也就是相當于C語言里的字符串，只不過這里字符串從1開始存取。

此外串里包含子串，每個字串的第一個元素位置為該字串在串中的位置，每個串里面必有一個空串，此外，數串的時候，遇到重復的，只保留一個。

kmp算法就是根據相應的字串（模式串）取查找相應位置的操作，

串的長度，實際上為字符串長度。而數組長度為串的長度+1+1，從數組1開始存，因此+1，最后字符串結尾\'0’也要存。

二、串的存儲結構：

靜態順序存儲，就是定義一個固定長度的字符數組，再多一個記錄個數的變量。

堆分配存儲，就是動態數組，malloc一個空間，空間大小為sizeof（char）*(max+2);

塊鏈存儲：就是單鏈表的基礎上，多了好多存儲數據的變量，因此一塊結點，好幾個變量存進去。

串的基本操作：
SteCompare(S,T),就是C語言里的字符串比較，實際操作為：S-T，若結果小于0，則S<T，若結果大于0，則S大于T，S、T為字符串。

Concat(*T,S1,S2),給S2連接到S1后面，組成新的串，賦值給T串，返回。

SubStrin(*Sub,S,pos,len)，返回串S中，第pos位置起，長度為len的字串

Index（S,T,Pos），模式匹配，S中第pos位置起，與字串T相等的串。并返回該串再S中出現的第一次的位置。

三、模式匹配

1.簡單模式匹配（BF算法）

模式匹配，就是有一個字串（模式串），取對應的主串里，找與它一樣的，并返回它在主串中的位置，

簡單模式匹配，就是主串在上，模式串在下，動主串坐標，取挨個對比。

設i為記錄主串的下標，j為模式串的下標，k則是記錄每次回溯，比對的次數。

當i和j中的值都相等時，都往后移動，當不匹配時，則進行下標的更新，主串中的i，更新為i=k+1，即主串的i從左至右，挨個比對，第一個開始，比對失敗，則第二個開始，重新比對。模式串則時更新為j=1，因為，每次重新比對，所以，模式串每次更新都是從1開始。

簡單模式匹配算法為（m*n）,主串長為m，模式串為n，因為最壞的情況，每次主串都要重新比對，所以為m，而每次比對，模式串都需要從頭到尾重新遍歷，所以m*n

2.KMP算法

????????kmp時間復雜度為O（m+n），KMP算法主要是模式串下標動，更新，主串中的i會一直增加，不會出現回溯的現象。

2.1-next（j）數組手工求解

? ? ? ? 在簡單模式匹配的基礎上，優化。即next（j）數組，是記錄，每次模式串比對失敗時，模式串下標的更新的起始值。如果模式串下標j==0，則i++，j++，即簡單匹配操作，否則，主串不需要動，模式串下標更新動即可。

? ? ? ? 而next(j)數組，怎么求嘞，next數組，就是給模式串每一個位置處，匹配失敗，時，跟新的下標值都記錄下來。所以手工怎么計算呢？

? ? ? ? 分兩部分，當第一個位置處時，j直接更新為0，因為第一個位置前，無數據，沒法拿來進行找重復部分的長度。第二個位置時，則找第一個位置，然后錯一位，進行比對，比對時，下面的那一串向右移動，直到比對完重復部分，之后重復部分長度+1，便是模式串下標所更新的值。

具體看講義，不好畫圖

2.2-nextval（j）數組手工求解

? ? ? ? nextval數組，則是在，next的基礎上，再優化。即，當next數組求的坐標的內容，與原來不匹配的坐標內容一致時，可直接，給nextval中，當前不匹配情況，與所求最新的，坐標相同即可。

具體看講義，不好畫圖。