字串演算法

**字串**（英語：string），是由零個或多個字元組成的有限序列。一般記為 $s=a_{1}a_{2}\dots a_{n}$ （ $0\leq n\lneq \infty $ ）。它是程式語言中表示文字的資料型別。

通常以串的整體作為運算物件，如：在串中尋找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。兩個字串相等的充要條件是：長度相等，並且各個對應位置上的字元都相等。設 p、q 是兩個串，求 q 在 p 中首次出現的位置的運算叫做模式匹配。串的兩種最基本的儲存方式是順序儲存方式和連結儲存方式。

## 形式理論

設 Σ 是叫做字母表的非空有限集合。Σ 的元素叫做「符號」或「字元」。在 Σ 上的**字串**（或**字**）是來自 Σ 的任何有限序列。例如，如果 Σ = {0, 1}，則 _0101_ 是在 Σ 之上的字串。

字串的長度是在字串中字元的數目（序列的長度），它可以是任何非負整數。「空字串」是在 Σ 上的唯一的長度為 0 的字串，並被指示為 _ε_ 或 _λ_。

在 Σ 上的所有長度為 _n_ 的字串的集合指示為 Σn。例如，如果 Σ = {0, 1} 則 Σ2 = {00, 01, 10, 11}。注意 Σ0 = {ε} 對於任何字母表 Σ。

在 Σ 上的所有任何長度的字串的集合是 Σ 的 Kleene 閉包並被指示為 Σ\*。依據 Σn, 

　
: $\Sigma ^{*}=\bigcup _{n=0}^{\infty }\Sigma ^{n}$ 。

例如，如果 Σ = {0, 1}，則 Σ\* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,…}。儘管 Σ\* 自身是可數無限的，Σ\* 的所有元素都有有限長度。

在 Σ 上一個字串的集合（就是 Σ\* 的任何子集）被稱為在 Σ 上的形式語言。例如，如果 Σ = {0, 1}，則帶有偶數個零的字串的集合（{ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111,…}）是在 Σ 上的形式語言。

### 串接和子串

「串接」（英語：_concatenation_）是 Σ\* 上的重要二元運算。對於 Σ\* 中的兩個字串 _s_ 和 _t_，它們的串接被定義為在 _s_ 中的字元序列之後跟隨著 _t_ 中的字元序列，並被指示為 _st_。例如，Σ = {a, b,…, z}，並且 _s_ = bear 且 _t_ = hug，則 _st_ = bearhug 而 _ts_ = hugbear。

字串串接是結合性的，但非交換性運算。空字串充當單位元；對於任何字串 _s_，有 ε_s_ = _s_ε = _s_。所以，集合 Σ\* 和串接運算形成了么半群，就是從 Σ 生成的自由么半群。此外，長度函式定義了一個從 Σ\* 到非負整數的么半群同態。

字串 _s_ 被稱為是字串 _t_ 的「子串」（英語：_substring_）或「因子」（英語：_factor_），如果存在（可能為空）字串 _u_ 和 _v_ 使得 _t_ = _usv_。「是其子串」關係定義了在 Σ\* 上的偏序，其最小元是空字串。

### 詞典排序

經常需要定義在字串集合上的次序。如果字元表 Σ 有一個全序（cf. 字母序），則可以定義在 Σ\* 上的叫做詞典序的全序。注意因為 Σ 是有限的，總是可以定義在 Σ 繼而在 Σ\* 上的良好次序。例如，如果 Σ = {0, 1} 並且 0 < 1，則 Σ\* 的詞典次序是 ε < 0 < 00 < 000 <…< 011 < 0110 <…< 01111 <…< 1 < 10 < 100 <…< 101 <…< 111…

### 字串運算

在形式理論中經常出現一些在字串上的額外運算。它們在條目字串運算中給出。

## 字串資料類型

**字串資料類型**是建模在形式字串的想法上的資料類型（Data type）。字串是幾乎在所有程式語言中都可以實現的非常重要和有用的資料類型。在某些語言中它們可作為基本類型獲得，在另一些語言中做為複合類型獲得。多數高階語言的語法允許用某種方式參照起來的字串來表示字串資料類型的實例；這種元字串叫做「常值」（英語：_literal_）或「字串常值」（英語：_string literal_）。

### 字串長度

儘管形式字串可以有任意（但有限）的長度，實際語言的字串的長度經常被限制到一個人工極大值。一般的說，有兩種類型的字串資料類型：「定長字串」，它有固定的極大長度並且不管是否達到了這個極大值都使用同樣數量的記憶體；和「變長字串」，它的長度不是專斷固定的並且依賴於實際的大小使用可變數量的記憶體。在現代程式語言中的多數字串是變長字串。儘管叫這個名字，所有變長字串還是在長度上有個極限，一般的說這個極限只依賴於可獲得的記憶體的數量。

### 字元編碼

歷史上，字串資料類型為每個字元分配一個位元組，儘管精確的字元集隨著區域而改變，字元編碼足夠類似得程式設計師可以忽略它 — 同一個系統在不同的區域中使用的字元集組要麼讓一個字元在同樣位置，要麼根本就沒有它。這些字元集典型的基於 ASCII 碼或 EBCDIC 碼。

意音文字的語言比如漢語、日語和韓語（合稱為 CJK）的合理表示需要多於 256 個字元（每字元一個位元組編碼的極限）。常規的解決涉及：保持對 ASCII 碼的單位元組表示，並使用雙位元組來表示 CJK 字形。現存代碼在用到它們會導致一些字串匹配和切斷上的問題，嚴重程度依賴於字元編碼是如何設計的。

1. 某些編碼比如 EUC 家族保證在 ASCII 碼範圍內的位元組值只表示 ASCII 字元，使得使用這些字元作為欄位分隔符的系統得到編碼安全。其他編碼如 ISO-2022 和 Shift-JIS 不做這種擔保，使得基於位元組的代碼做的匹配不安全。
2. 另一個問題是如果一個字串的開頭被刪除了，對解碼器的重要指示或關於在多位元組序列中的位置的資訊可能就遺失了。
3. 另一個問題是如果字串被連接到一起（特別是在被不知道這個編碼的代碼截斷了它們的結尾之後），第一個字串可能不能導致編碼器進入適合處理第二個字串的狀態中。

Unicode 也有些複雜的問題。多數語言有 Unicode 字串資料類型（通常是 UTF-16，因為它在 Unicode 補充位面介入之前就被增加了）。在 Unicode 和本地編碼之間轉換要求理解本地編碼，這對於現存系統要一起傳輸各種編碼的字串而又沒有實際標記出它們用了什麼編碼就是個問題。

### 實現

某些語言如 C++ 把字串實現為可以用於任何基本類型的模版，但這是個例外而不是規則。

在一個物件導向語言把字串表示為物件的情況下，如果值可以在執行期變更，則叫做「可變的」（mutable），如果值在建立後就不可變更了，則叫做「不變的」（immutable）。例如，Ruby 有可變字串，而 Python 的字串是不可變的。

其他語言，最著名的有 Prolog 和 Erlang，避免實現字串資料類型，轉而採用把字串表示為字元代碼的列表的約定。

### 表示法

一種常用的表示法是使用一個字元代碼的陣列，每個字元占用一個位元組（如在 ASCII 代碼中）或兩個位元組（如在 unicode 中）。它的長度可以使用一個結束符（一般是 NUL，ASCII 代碼是 0，在 C 程式語言中使用這種方法）。或者在前面加入一個整數值來表示它的長度（在 Pascal 語言中使用這種方法）。

這是一個用 NUL 結束的字串的例子，它用 10 個 byte 儲存，用 ASCII 表示法：

上面的字串的長度為 5 個字元，但注意它占用 6 個位元組。結束符後的字元沒有任何意義。

這是相同的 Pascal 字串：

當然，可能還有其它的表示法。使用樹和列表可以使得一些字串操作（如插入和刪除）更高效。

## 字串實用程式

一些程式語言設計為編寫字串處理程式更容易編寫。這是一些例子：

* awk
* Icon
* perl
* MUMPS
* sed
* SNOBOL

很多 UNIX 實用程式進行簡單的字串處理，並能用於簡單地編寫一些強大的字串處理演算法。檔案和有限流可以像字串一樣檢視。

一些新的程式語言，包括 Perl、Python 和 Ruby，藉助正規表示式來幫助文書處理。

## 演算法

這是一些字串處理演算法，在字串上進行不同的處理：

* 字串尋找演算法
* 排序演算法
* 正規表示式演算法
* 模式匹配

## 參見

* string —— C++ 字串處理
* string.h —— C 語言字串處理
* 空字串
* 正規表示式

## 參考資料