字元數組子串引用

字元數組用於存放字元或字元串，字元數組中的一個元素存放一個字元，它在記憶體中占用一個位元組。字元數組子串引用是指應用程式對字元串中子串的引用。在實際套用中，經常需要對字元串進行匹配和查找等操作，需要對字元數組子串進行引用。

基本介紹

• 中文名：字元數組子串引用
• 外文名：character array substring reference
• 學科：計算機
• 有關術語：子串
• 目的：字元串引用、匹配
• 領域：計算機編程

簡介

數組是一種特殊的對象類型，其中可以保存一個有序的元素集合。數組元素的類型 稱為該數組的基類型(base type)；其中保存的元素個數是一個固定的屬性，稱為其長度(length)。字元數組子串引用是指應用程式對字元數組中子串的引用。在實際套用中，有時候需要對字元串一個子串進行引用，來判斷這個字元數組是否滿足需求。字元數組子串引用需要對字元數組中字元串經過查找匹配等過程，其中匹配算法的好壞直接影響字元數組子串引用的性能，例如時間代價、空間代價。

有關術語

字元變數

字元常數的一般形式是由一對單引號‘ ’或一對雙引號“”限定的一串字元。字元串中的字元，允許是PORTRAN字元集的任意字元，如果系統還支持其它字元，例如漢字、希臘字、化學符號、數學符號，也可引入字元串內，用一對‘ ’或“”界定。

字元型數據除了有類型、種別外，比其它類型還多了一個長度特性，即規定它有幾個字元數。字元型說明語句的關鍵字是CHARACTER，其長度說明方法是緊跟在CHARACTER後面寫一對括弧，括弧內寫LEN=字元長度。其一般形式是：

CHARACTER[(LEN=整型字元長度表達式[,KIND=種別值])][,屬性說明] ::變數名表[=初始值]

其中LEN後面的整常數表達式規定被說明字元變數長度，為正整數，LEN的參數與KIND的參數都寫在括弧內，次序可以任意。在字元型說明語句中，長度說明必須有，不可省略，種別參數可以省略，此時取標準值。僅有關鍵字CHARACTER而沒有括弧時認為字元是一個位元組長。可以省去LEN=及KTND=，只寫參數值，此時字元長度必須寫在前面。只有長度說明的語句可分為有括弧和無括弧兩種，例如：

CHARACTER(LEN=12,KIND=1) :: A,B

CHARACTER(KIND=1,LEN=12) :: A,B

CHARACTER(12,1) :: A,B

CHARACTER*12 :: A,B

都是等價的，前者說明X、Y2是字元型變數，種別參數為3．每個變數長度為12。後者說明表明長度為12，種別值為1。

長度也可以寫成一個*號，表示長度暫不確定，待以後與程式中實際需要的長度相一致。例如：

CHARACTER(LEN=*),PARAMETER :: C_NAME=‘GIRL’

CHARACTER(LEN=*),PARAMETER :: C_NAME=‘BOY’

都是合法的說明語句，說明字元常量C_NAME，前者長度為4，後者長度為3。

用字元型變數作為過程的啞元時，可以用正整數作長度，也可以把*作長度，後者可以與任何長度的實元作啞實結合，相當於以實元的具體長度為啞元的長度。

CHARACTER後面說明的長度是其後所有實體名的公共長度，如果某一變數的長度與其它不同，可以在其變數名後標出自己的特有長度，方法是在變數名後寫上*及長度。例加：

CHARACTER(LEN=12) :: A,B*5,C,D*7,E

字元子串

字元數據中某一部分相連的字元為字元子串，也可以作為一個實體與字元變數一樣參加操作。字元子串的一般形式是：V(e1:e2)。V是字元型實體名，包括字元變數名、字元函式名、字元數組元素等等。e1,e2是整型表達式或正整常數，e1的值指明子串在V中的起始列號，e2的值指明子串在V中的終止列號。如果e1省略，表示子串從第一個字元取起；e2省略，表示子串取到末尾；如e1,e2都省略，表示子串從頭取到尾。例如：設有字元變數A，其取值為‘ABCDE12345FGH’，則下面的子串取值為：

A(3:11)->‘CDE12345F’，

A(I+4:9)->‘E1234’(I=1)，‘1234’(I=2)

A(:5)->‘ABCDE’

A(11:)->‘FGH’

A(:)->‘ABCDE12345FGH’

A(3:3)->‘C’

子串在程式中可直接引用，也可被其它字元實體再賦值，因此可使程式設計師任意地取出一部分字元，並按需要替換一部分字元，非常靈活。例如：PRINT *，(A(I:I+1),I=6,9)，可以列印‘12’、‘23’、‘34’、‘45’。

匹配方法

近似匹配

近似匹配是一種允許誤差的串匹配。這種誤差的度量一般用編輯距離，記為k。衡量編輯距離的操作包括插入、刪除、替換。問題的輸入是文本T，模式P和編輯距離k，輸出是匹配數或匹配位置。常用的方法包括動態規劃、自動機、位並行和過濾算法。近似匹配也屬於Non-standard Stringology問題。它最常見的套用背景來源於生物信息學。問題定義上，近似匹配中的k可以對模式中的任何字元的編輯操作進行計數。例如，給定文本T的子串T’= ……aacct……，P = aaacc，從P到T’要經過兩次替換操作，因此k= 2。

樸素的模式匹配算法

算法思想：從目標串的的第一個字元起與模式串的第一個字元比較，若相等，則繼續對字元進行後續的比較，否則目標串從第二個字元起與模式串的第一個字元重新比較，直至模式串中的每個字元依次和目標串中的一個連續的字元序列相等為止，此時稱為匹配成功，否則匹配失敗。

若模式子串的長度是m,目標穿的長度是n，這時最壞的情況是每遍比較都在最後出現不等，即沒變最多比較m次，最多比較n-m+1遍，總的比較次數最多為m(n-m+1)，因此樸素的模式匹配算法的時間複雜度為O(mn)。樸素的模式匹配算法中存在回溯，這影響到匹配算法的效率，因而樸素的模式匹配算法在實際套用中很少採用。在實際套用主要採用無回溯的匹配算法，KMP算法和BM算法均為無回溯的匹配算法。

KMP匹配算法

Knuth-Morris-Pratt算法（簡稱KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一個改進算法，消除了樸素的模式匹配算法中回溯問題，完成串的模式匹配。

算法思想：

設目標串為s，模式串為t， i、j 分別為指示s和t的指針，i、j的初值均為0。

若有 si = tj，則i和j分別增1；否則，i不變，j退回至j=next[j]的位置 ( 也可理解為串s不動，模式串t向右移動到si與tnext[j]對齊 )；

比較si和tj。若相等則指針各增1；否則 j 再退回到下一個j=next[j]的位置(即模式串繼續向右移動 )，再比較 si和tj。

依次類推，直到下列兩種情況之一：

1)j退回到某個j=next[j]時有 si = tj，則指針各增1，繼續匹配；

2)j退回至 j=-1，此時令指針各增l，即下一次比較 si+1和 t0。

記模式P的長度為m,目標T的長度為n,則KMP匹配算法的時間複雜度的分析如下：

整個匹配算法由Find()和GenKMPNext()兩部分算法組成。在Find()中包含一個循環,J的初值為0，每循環一次j的值嚴格家1，指導j等於n時循環結束，故循環執行了n次。在GenKMPNext()中，表面上有兩重循環，時間複雜度似乎為O(),其實不然，GenKMPNext()的外層循環恰好執行了m-1次；另外，j的初值為-1，外層循環中，每循環一次，j的值就加1，同時，在內層循環中j減小，但最少不會小於-1，因此內層循環中j=next[j]的語句的總的執行次數應小於或等於j的值在外層循環中被加2 的次數。即在算法GenKMPNext()結束時，j=next[j]的執行總次數小於等於m-1次。

綜上，對於長度為m的模式和長度為n的目標T的模式匹配，KMP算法的時間複雜度為O(m+n)。

Boyer-Moore字元串搜尋算法

Boyer-Moore字元串搜尋算法是一種非常高效的字元串搜尋算法。它由Bob Boyer和J Strother Moore設計於1977年。此算法僅對搜尋目標字元串（關鍵字）進行預處理，而非被搜尋的字元串。雖然Boyer-Moore算法的執行時間同樣線性依賴於被搜尋字元串的大小，但是通常僅為其它算法的一小部分：它不需要對被搜尋的字元串中的字元進行逐一比較，而會跳過其中某些部分。通常搜尋關鍵字越長，算法速度越快。它的效率來自於這樣的事實：對於每一次失敗的匹配嘗試，算法都能夠使用這些信息來排除儘可能多的無法匹配的位置。定義如下：

S[i]為字元串S從1開始排列的第i個字元

S[i..j]為字元串S的一個子串，始於i，終於j。

S的前綴定義為S[1..i],1<i<n，n為字元串S的長度。

S的後綴定義為S[i..n],1<i<=n，小於字元串S的長度。

檢索的字元串稱為pattern，用符號P表示。

被檢索字元稱為test，用符號T表示。

P的長度為n

T的長度為m

k表示P的最後一個字元在T中的位置。

當匹配發生時，P在T中的位置為T[(k-n+1)..k]。

不同於樸素模式（brute-force search）的逐個字元對比，Boyer-Moore充分使用預處理P的信息來儘可能跳過更多的字元。通常，我們比較一個字元串都是從首字母開始，逐個比較下去。一旦發現有不同的字元，就需要從頭開始進行下一次比較。這樣，就需要將字串中的所有字元一一比較。Boyer-Moore算法的關鍵在於，當P的最後一個字元被比較完成後，我們可以決定跳過一個或更多個字元。如果最後一個字元不匹配，那么就沒必要繼續比較前一個字元。如果最後一個字元未在P中出現，那么我們可以直接跳過T的n個字元，比較接下來的n個字元，n為P的長度（見定義）。如果最後一個字元出現在P中，那么跳過的字元數需要進行計算（也就是將P整體往後移），然後繼續前面的步驟來比較。通過這種字元的移動方式來代替逐個比較是這個算法如此高效的關鍵所在。

形式化的表述方式為，從k=n開始，也就是P從T的最開始進行比較。緊接著，P的第n個字元和T的第k個字元開始：字元串依次從P的最後一個字元到最開始的字元。結束條件是當比較到達P的最開始（此時匹配完成），或按照規則移動後的字元部匹配發生時。然後，在新的對齊位置重新開始比較，如此反覆，直到到達T的結尾。

移動規則是一張間恆定的查找表，通過對P的預處理產生的。