第5章 串

串（string）是由零個或多個字符組成的有限序列，又名叫字符串。

串的定義

串（string）是由零個或多個字符組成的有限序列，又名叫字符串。

串的比較

給定兩個串：s= "a₁a₂……a_n", t= "b₁b₂……b_m", 當滿足以下條件之一時，s<t。

1. n<m，且a_i=b_i（i=1, 2, ……, n）。
2. 存在某個k<min(m, n), 使得a_i=b_i（i=1，2，……，k-1）a_k<b_k

串的抽象數(shù)據(jù)類型

ADT 串（string）
Data
  串中元素僅由一個字符組成，相鄰元素具有前驅(qū)和后繼關(guān)系。
Operation
  StrAssign(T,*chars):生成一個其值等于字符串常量chars的串T。
  StrCopy(T,S):串S存在，由串復制得串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 */
}

當中用到了 StrLength、SubString、StrCompare 等基本操作來實現(xiàn)。

串的存儲結(jié)構(gòu)

串的順序存儲結(jié)構(gòu)

串的順序存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元來存儲串中的字符序列的。按照預定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。一般使用定長數(shù)組來定義。

串的鏈式存儲結(jié)構(gòu)

對于串的鏈式存儲結(jié)構(gòu)，與線性表是相似的，但由于串結(jié)構(gòu)的特殊性，結(jié)構(gòu)中的每個元素數(shù)據(jù)是一個字符，如果也簡單的應用鏈表存儲串值，一個結(jié)點對應一個字符，就會存在很大的空間浪費。因此，一個結(jié)點可以存放一個字符，也可以考慮存放多個字符，最后一個結(jié)點若是未被占滿時，可以用“#”或其他非串值字符補全。

串的鏈式存儲結(jié)構(gòu)除了在鏈接串與串操作時有一定方便外，總的來說不如順序存儲靈活，性能也不如順序存儲結(jié)構(gòu)好。

樸素的模式匹配算法

子串的定位操作通常稱做串的模式匹配。
假設我們要從下面的主串S=“goodgoogle”中，找到T=“google這個子串的位置”。
簡單的來說，就是對主串的每一個字符作為子串開頭，與要匹配的字符串進行匹配。對主串做大循環(huán)，每個字符開頭做T的長度的小循環(huán)，直到匹配成功或全部遍歷完成為止。
最好的情況，時間復雜度為O(1)。
稍差一些的情況，時間復雜度為O(n+m)，其中n為主串長度，m為要匹配的子串長度。
根據(jù)等概率原則，平均是(n+m)/2次查找，時間復雜度為O(n+m)。

KMP模式匹配算法

D.E.Knuth、J.H.Morris 和 V.R.Pratt 發(fā)表一個模式匹配算法，可以大大避免重復遍歷的情況，我們把它稱之為克努特-莫里斯-普拉特算法，簡稱 KMP 算法。