第5章 串
串（string）是由零個或多個字符組成的有限序列漠嵌，又名叫字符串募逞。
串的定義
串（string）是由零個或多個字符組成的有限序列鬼譬，又名叫字符串焚鹊。
串的比較
給定兩個串：s= "a1a2……an", t= "b1b2……bm", 當(dāng)滿足以下條件之一時，s<t衡瓶。
- n<m徘公，且ai=bi（i=1, 2, ……, n）。
- 存在某個k<min(m, n), 使得ai=bi（i=1哮针，2关面，……坦袍，k-1）ak<bk
串的抽象數(shù)據(jù)類型
ADT 串（string）
Data
串中元素僅由一個字符組成，相鄰元素具有前驅(qū)和后繼關(guān)系缭裆。
Operation
StrAssign(T,*chars):生成一個其值等于字符串常量chars的串T。
StrCopy(T,S):串S存在寿烟，由串復(fù)制得串T澈驼。
ClearString(S):串S存在，將串清空筛武。
StringEmpty(S):若串為空缝其，返回true，否則返回false徘六。
StrLength(S):返回串S的元素個數(shù)内边，即串的長度。
StrCompare(S,T):若S>T待锈，返回值>0,若S=T漠其，返回0，若S<T竿音，返回值<0.
Concat(T,S1,S2):用T返回由S1和S2聯(lián)接而成的新串和屎。
SubString(Sub,S,pos,len):串S存在，1<=pos<=StrLength(S)春瞬，且0<=len<=StrLength(S)-pos+1,用Sub返回串S的第pos個字符長度為len的子串柴信。
Index(S,T,pos):串S和T存在，T是非空串宽气，1<=pos<=StrLength(S)随常。若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置萄涯，否則返回0绪氛。
Replace(S,T,V):串S、T和V存在涝影，T是非空串钞楼。用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。
StrInsert(S,pos,T):串S和T存在袄琳，1<=pos<=StrLength(S)+1询件。在串S的第pos個字符之前插入串T。
StrDelete(S,pos,len):串S存在唆樊，1<=pos<=StrLength(S)-len+1宛琅。從串S中刪除第pos個字符起長度為len的子串。
endADT
Index 的實現(xiàn)算法
/* 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; /* 若無子串與T相等，返回0 */
}
當(dāng)中用到了 StrLength红伦、SubString英古、StrCompare 等基本操作來實現(xiàn)。
串的存儲結(jié)構(gòu)
串的順序存儲結(jié)構(gòu)
串的順序存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元來存儲串中的字符序列的昙读。按照預(yù)定義的大小召调，為每個定義的串變量分配一個固定長度的存儲區(qū)。一般使用定長數(shù)組來定義蛮浑。
串的鏈?zhǔn)酱鎯Y(jié)構(gòu)
對于串的鏈?zhǔn)酱鎯Y(jié)構(gòu)唠叛，與線性表是相似的，但由于串結(jié)構(gòu)的特殊性沮稚，結(jié)構(gòu)中的每個元素數(shù)據(jù)是一個字符艺沼，如果也簡單的應(yīng)用鏈表存儲串值，一個結(jié)點對應(yīng)一個字符蕴掏，就會存在很大的空間浪費障般。因此，一個結(jié)點可以存放一個字符盛杰，也可以考慮存放多個字符剩拢，最后一個結(jié)點若是未被占滿時，可以用“#”或其他非串值字符補全饶唤。
串的鏈?zhǔn)酱鎯Y(jié)構(gòu)除了在鏈接串與串操作時有一定方便外徐伐，總的來說不如順序存儲靈活，性能也不如順序存儲結(jié)構(gòu)好募狂。
樸素的模式匹配算法
子串的定位操作通常稱做串的模式匹配办素。
假設(shè)我們要從下面的主串S=“goodgoogle”中，找到T=“google這個子串的位置”祸穷。
簡單的來說性穿，就是對主串的每一個字符作為子串開頭，與要匹配的字符串進行匹配雷滚。對主串做大循環(huán)需曾，每個字符開頭做T的長度的小循環(huán)，直到匹配成功或全部遍歷完成為止祈远。
最好的情況呆万，時間復(fù)雜度為O(1)。
稍差一些的情況车份，時間復(fù)雜度為O(n+m)谋减，其中n為主串長度，m為要匹配的子串長度扫沼。
根據(jù)等概率原則出爹，平均是(n+m)/2次查找庄吼，時間復(fù)雜度為O(n+m)。
KMP模式匹配算法
D.E.Knuth严就、J.H.Morris 和 V.R.Pratt 發(fā)表一個模式匹配算法总寻，可以大大避免重復(fù)遍歷的情況，我們把它稱之為克努特-莫里斯-普拉特算法梢为，簡稱 KMP 算法渐行。
