字串

字串（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字形。現存代碼在用到它們會導致一些字串匹配和切斷上的問題，嚴重程度依賴於字符編碼是如何設計的。

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

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

### 實現

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

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

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

### 表示法

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

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

F｜R｜A｜N｜K｜NUL｜k｜e｜f｜w

46｜52｜41｜4E｜4B｜00｜6B｜66｜66｜77

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

這是相同的Pascal字串：

length｜F｜R｜A｜N｜K｜k｜e｜f｜w

05｜46｜52｜41｜4E｜4B｜6B｜66｜66｜77

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

## 字串實用程序

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

- awk
- Icon
- perl
- MUMPS
- sed
- SNOBOL

很多UNIX實用程序進行簡單的字串處理，並能用於簡單地編寫一些強大的字串處理演算法。文件和有限流可以像字串一樣查看。

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

## 演算法

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

- 字串查找演算法
- 排序算法
- 正則表達式演算法
- 模式匹配