字串

字元串（String），是由零個或多個字元組成的有限串列。 s=“a1a2···an”(n>=0)。它是程式語言中表示文本的數據類型。

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

基本介紹

• 中文名：字元串
• 外文名：String

基本信息

字元串（String），是由零個或多個字元組成的有限串列。s=“a1a2···an”(n>=0)。它是程式語言中表示文本的數據類型。

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

形式理論

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

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

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

在Σ上的所有任何長度的字元串的集合是Σ的Kleene閉包並被指示為Σ*。依據,。例如，如果Σ = {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,…}）是在Σ上的形式語言。

串接和子串

“串接”是Σ*上的重要二元運算。對於Σ*中的兩個字元串s和t，它們的串接被定義為在s中的字元串列之後跟隨著t中的字元串列，並被指示為st。例如，Σ = {a, b,…, z}，並且s=bear且t=hug，則st=bearhug而ts=hugbear。

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

字元串s被稱為是字元串t的“子串”或“因子”，如果存在（可能為空）字元串u和v使得t=usv。“是其子串”關係定義了在Σ*上的偏序，其最小元是空串。

詞典排序

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

字串運算

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