字符串
字符串（英语：string），是由零个或多个字符组成的有限序列。一般记为（）。它是编程语言中表示文本的数据类型。
通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存储方式是顺序存储方式和链接存储方式。
形式理论
[编辑]设Σ是叫做字母表的非空有限集合。Σ的元素叫做“符号”或“字符”。在Σ上的字符串（或字）是来自Σ的任何有限序列。[1]例如，如果Σ = {0, 1}，则0101是在Σ之上的字符串。
字符串的长度是在字符串中字符的数目（序列的长度），它可以是任何非负整数。“空串”是在Σ上的唯一的长度为0的字符串，并被指示为ε或λ。[1][2]
在Σ上的所有长度为n的字符串的集合指示为Σn。例如，如果Σ = {0, 1}则Σ2 = {00, 01, 10, 11}。注意Σ0 = {ε}对于任何字母表Σ。
在Σ上的所有任何长度的字符串的集合是Σ的Kleene闭包并被指示为Σ*。依据Σ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编程语言中使用这种方法）。[3]或者在前面加入一个整数值来表示它的长度（在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 |
当然，可能还有其它的表示法。使用树和列表可以使得一些字符串操作（如插入和删除）更高效。
字符串实用程序
[编辑]一些编程语言设计为编写字符串处理程序更容易编写。这是一些例子：
很多UNIX实用程序进行简单的字符串处理，并能用于简单地编写一些强大的字符串处理算法。文件和有限流可以像字符串一样查看。
一些新的编程语言，包括Perl、Python和Ruby，借助正则表达式来帮助文字处理。
算法
[编辑]这是一些字符串处理算法，在字符串上进行不同的处理：
参见
[编辑]参考资料
[编辑]- ^ 1.0 1.1 Barbara H. Partee; Alice ter Meulen; Robert E. Wall. Mathematical Methods in Linguistics. Kluwer. 1990.
- ^ John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. 1979. ISBN 0-201-02988-X. Here: sect.1.1, p.1
- ^ Bryant, Randal E.; David, O'Hallaron, Computer Systems: A Programmer's Perspective 2003, Upper Saddle River, NJ: Pearson Education: 40, 2003 [2019-04-15], ISBN 0-13-034074-X, （原始内容存档于2007-08-06）