形式理论

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

字符串的长度是在字符串中字符的数目（序列的长度），它可以是任何非负整数。“空串”是在Σ上的唯一的长度为0的字符串，并被指示为 ε 或 λ 。

在Σ上的所有长度为 n 的字符串的集合指示为Σ 。例如，如果Σ = {0, 1}则Σ = {00, 01, 10, 11}。注意Σ = {ε}对于任何字母表Σ。

在Σ上的所有任何长度的字符串的集合是Σ的Kleene闭包并被指示为Σ*。依据Σ , Σ Σ --> ∗ ∗ --> = ⋃ ⋃ --> n = 0 ∞ ∞ --> Σ Σ --> n {\displaystyle \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,…}）是在Σ上的形式语言。

串接和子串

“串接”是Σ*上的重要二元运算。对于Σ*中的两个字符串 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

字符串运算

在形式理论中经常出现一些在字符串上的额外运算。它们在条目字符串运算中给出。

字符串数据类型

字符串数据类型 是建模在形式字符串的想法上的数据类型（ Data type ）。字符串是几乎在所有编程语言中可以实现的非常重要和有用的数据类型。在某些语言中它们可作为基本类型获得，在另一些语言中做为复合类型获得。多数高级语言的语法允许通常用某种方式引用起来的字符串来表示字符串数据类型的实例；这种元字符串叫做“文字”或“字符串文字”。

字符串长度

尽管形式字符串可以有任意（但有限）的长度，实际语言的字符串的长度经常被限制到一个人工极大值。一般的说，有两种类型的字符串数据类型：“定长字符串”，它有固定的极大长度并且不管是否达到了这个极大值都使用同样数量的内存；和“变长字符串”，它的长度不是专断固定的并且依赖于实际的大小使用可变数量的内存。在现代编程语言中的多数字符串是变长字符串。尽管叫这个名字，所有变长字符串还是在长度上有个极限，一般的说这个极限只依赖于可获得的内存的数量。

字符编码

历史上，字符串数据类型为每个字符分配一个字节，尽管精确的字符集随着区域而改变，字符编码足够类似得程序员可以忽略它—同一个系统在不同的区域中使用的字符集组要么让一个字符在同样位置，要么根本就没有它。这些字符集典型的基于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表示法：

上面的字符串的长度为5个字符，但注意它占用6个字节。结束符后的字符没有任何意义。

这是相同的Pascal字符串：

当然，可能还有其它的表示法。使用树和列表可以使得一些字符串操作（如插入和删除）更高效。

字符串实用程序

一些编程语言设计为编写字符串处理程序更容易编写。这是一些例子：

awk

Icon

perl

MUMPS

sed

SNOBOL

很多UNIX实用程序进行简单的字符串处理，并能用于简单地编写一些强大的字符串处理算法。文件和有限流可以像字符串一样查看。

一些新的编程语言，包括Perl、Python和Ruby，借助正则表达式来帮助文字处理。

字符串操作

一个简单的字符串操作是“连接”：也就是说先写一个字符串 S ，随后在后面再写一个 T 得到 ST 这样一个过程。 其它的常见操作包括在一个长字符串中搜索一个子串，排列一组字符串以及分析一个字符串。因为存在如此多的字符串应用方式，所以相应地有许多权衡了不同应用的相关算法。 高级的字符串算法通常使用包括后向树和有限状态机在内的复杂机制和数据结构。

算法

这是一些字符串处理算法，在字符串上进行不同的处理：

字符串查找算法

正则表达式算法

模式匹配

参见

正则表达式

SQL语言的模式匹配

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。