### 一、串的定義
串（string）是由零個或多個字符組成的有限序列，又名叫字符串。
一般記作： s="a1a2a3...an";
字符串的基本操作方法：
### 二、串的存儲結構
1.串的順序存儲結構：串的順序存儲結構是用一組地址連續的存儲單元來存儲串中的字符序列的。
2.串的鏈式存儲結構：總的來說不如順序存儲靈活，性能也不如順序存儲結構好。
### 三、樸素的模式匹配算法
子串的定位操作通常稱作串的模式匹配，是串中最重要的操作之一。
算法如下：
~~~
/*操作Index的實現算法*/
//T為非空串。若主串S中第pos個字符之后存在與T相等的子串，則返回第一個這樣的子串，則返回第一個這樣的子串在S中的位置，否則返回0
int Index(String S,String T,int pos)
{
int n,m,i;
String sub;
if (pos > 0)
{
n = StrLength(S);
m = StrLength(T);
i = pos;
while (i <= n-m+1)
{
SubString (sub,S,i,m); //取主串第i個位置，長度與T相等子串給sub
if (StrCompare(sub,T) != 0) //如果不相等
++i;
else
return i;
}
}
return 0;
}
~~~
###
四、KMP模式匹配算法
我們可以忍受樸素模式匹配算法的低效嗎?也許不可以，也許無所謂。但在很多年前我們的科學家們，覺得像這種有多個0和1重復字符的字符串，卻需要挨個遍歷的算法是非常糟糕的事情。于是有三位前輩，發表一個模式匹配算法，可以大大避免重復遍歷的情況，我們把它稱為KMP算法。
kmp算法完成的任務是：給定兩個字符串O和f，長度分別為n和m，判斷f是否在O中出現，如果出現則返回出現的位置。常規方法是遍歷a的每一個位置，然后從該位置開始和b進行匹配，但是這種方法的復雜度是O(nm)。kmp算法通過一個O(m)的預處理，使匹配的復雜度降為O(n+m)。?
#### kmp算法思想
我們首先用一個圖來描述kmp算法的思想。在字符串O中尋找f，當匹配到位置i時兩個字符串不相等，這時我們需要將字符串f向前移動。常規方法是每次向前移動一位，但是它沒有考慮前i-1位已經比較過這個事實，所以效率不高。事實上，如果我們提前計算某些信息，就有可能一次前移多位。假設我們根據已經獲得的信息知道可以前移k位，我們分析移位前后的f有什么特點。我們可以得到如下的結論：
- A段字符串是f的一個前綴。
- B段字符串是f的一個后綴。
- A段字符串和B段字符串相等。
所以前移k位之后，可以繼續比較位置i的前提是f的前i-1個位置滿足：**長度為i-k-1的前綴A和后綴B相同**。只有這樣，我們才可以前移k位后從新的位置繼續比較。
所以kmp算法的核心即是計算字符串f每一個位置之前的字符串的前綴和后綴公共部分的最大長度（不包括字符串本身，否則最大長度始終是字符串本身）。獲得f每一個位置的最大公共長度之后，就可以利用該最大公共長度快速和字符串O比較。當每次比較到兩個字符串的字符不同時，我們就可以根據最大公共長度將字符串f向前移動(已匹配長度-最大公共長度)位，接著繼續比較下一個位置。事實上，字符串f的前移只是概念上的前移，只要我們在比較的時候從最大公共長度之后比較f和O即可達到字符串f前移的目的。
#### next數組計算
理解了kmp算法的基本原理，下一步就是要獲得字符串f每一個位置的最大公共長度。這個最大公共長度在算法導論里面被記為next數組。在這里要注意一點，next數組表示的是長度，下標從1開始；但是在遍歷原字符串時，下標還是從0開始。假設我們現在已經求得next[1]、next[2]、……next[i]，分別表示長度為1到i的字符串的前綴和后綴最大公共長度，現在要求next[i+1]。由上圖我們可以看到，如果位置i和位置next[i]處的兩個字符相同（下標從零開始），則next[i+1]等于next[i]加1。如果兩個位置的字符不相同，我們可以將長度為next[i]的字符串繼續分割，獲得其最大公共長度next[next[i]]，然后再和位置i的字符比較。這是因為長度為next[i]前綴和后綴都可以分割成上部的構造，如果位置next[next[i]]和位置i的字符相同，則next[i+1]就等于next[next[i]]加1。如果不相等，就可以繼續分割長度為next[next[i]]的字符串，直到字符串長度為0為止。由此我們可以寫出求next數組的代碼（java版）：
**
~~~
public int[] getNext(String b)
{
int len=b.length();
int j=0;
int next[]=new int[len+1];//next表示長度為i的字符串前綴和后綴的最長公共部分，從1開始
next[0]=next[1]=0;
for(int i=1;i<len;i++)//i表示字符串的下標，從0開始
{//j在每次循環開始都表示next[i]的值，同時也表示需要比較的下一個位置
while(j>0&&b.charAt(i)!=b.charAt(j))j=next[j];
if(b.charAt(i)==b.charAt(j))j++;
next[i+1]=j;
}
return next;
}
~~~
上述代碼需要注意的問題是，我們求取的next數組表示長度為1到m的字符串f前綴的最大公共長度，所以需要多分配一個空間。而在遍歷字符串f的時候，還是從下標0開始(位置0和1的next值為0，所以放在循環外面)，到m-1為止。代碼的結構和上面的講解一致，都是利用前面的next值去求下一個next值。
#### 字符串匹配
計算完成next數組之后，我們就可以利用next數組在字符串O中尋找字符串f的出現位置。匹配的代碼和求next數組的代碼非常相似，因為匹配的過程和求next數組的過程其實是一樣的。假設現在字符串f的前i個位置都和從某個位置開始的字符串O匹配，現在比較第i+1個位置。如果第i+1個位置相同，接著比較第i+2個位置；如果第i+1個位置不同，則出現不匹配，我們依舊要將長度為i的字符串分割，獲得其最大公共長度next[i]，然后從next[i]繼續比較兩個字符串。這個過程和求next數組一致，所以可以匹配代碼如下（java版）：
~~~
public void search(String original, String find, int next[]) {
int j = 0;
for (int i = 0; i < original.length(); i++) {
while (j > 0 && original.charAt(i) != find.charAt(j))
j = next[j];
if (original.charAt(i) == find.charAt(j))
j++;
if (j == find.length()) {
System.out.println("find at position " + (i - j));
System.out.println(original.subSequence(i - j + 1, i + 1));
j = next[j];
}
}
}
~~~
上述代碼需要注意的一點是，每次我們得到一個匹配之后都要對j重新賦值。
#### 復雜度
kmp算法的復雜度是O(n+m)，可以采用均攤分析來解答，具體可參考算法導論。
