字じ符ふ串くし

字じ符ふ串くし（英語えいご：string），是ぜ由よし零れい个或多た个字じ符ふ组成的てき有限ゆうげん序列じょれつ。一般いっぱん记为$s=a_{1}a_{2}\dots a_{n}$（$0\leq n\lneq \infty$）。它是编程语言中ちゅう表示ひょうじ文ぶん本ほん的てき数かず据すえ类型。

通常つうじょう以串的てき整体せいたい作さく为操作そうさ对象，如：在ざい串くし中ちゅう查找某ぼう个子串くし、求もとめ取ど一いち个子串くし、在ざい串くし的てき某ぼう个位置いち上じょう插入そうにゅう一个子串以及删除一个子串等。两个字じ符ふ串くし相等そうとう的てき充たかし要よう条件じょうけん是ぜ：长度相等そうとう，并且各かく个对应位置いち上じょう的てき字じ符ふ都と相等そうとう。设p、q是ぜ两个串くし，求もとむq在ざいp中ちゅう首くび次じ出で现的位置いち的てき运算叫さけべ做模式しき匹ひき配はい。串くし的てき两种最さい基本きほん的てき存そん储方式しき是ぜ顺序存そん储方式しき和わ链接存そん储方式しき。

形式けいしき理り论

设Σしぐま是ぜ叫さけべ做字母じぼ表ひょう的てき非ひ空そら有限ゆうげん集合しゅうごう。Σしぐま的てき元素げんそ叫さけべ做“符号ふごう”或ある“字じ符ふ”。在ざいΣしぐま上うえ的てき字じ符ふ串くし（或ある字じ）是ぜ来き自じΣ的てき任にん何なん有限ゆうげん序列じょれつ。例れい如，如果Σしぐま = {0, 1}，则0101是ぜ在ざいΣしぐま之の上うえ的てき字じ符ふ串くし。

字じ符ふ串くし的てき长度是ぜ在ざい字じ符ふ串くし中ちゅう字じ符ふ的てき数すう目もく（序列じょれつ的てき长度），它可以是任にん何なに非ひ负整数すう。“空そら串くし”是ぜ在ざいΣしぐま上うえ的てき唯ただ一的长度为0的てき字じ符ふ串くし，并被指示しじ为εいぷしろん或あるλらむだ。

在ざいΣしぐま上うえ的てき所有しょゆう长度为n的てき字じ符ふ串くし的てき集合しゅうごう指示しじ为Σしぐまⁿ。例れい如，如果Σしぐま = {0, 1}则Σしぐま² = {00, 01, 10, 11}。注意ちゅういΣしぐま⁰ = {εいぷしろん}对于任にん何なん字母じぼ表ひょうΣしぐま。

在ざいΣしぐま上うえ的てき所有しょゆう任にん何なん长度的てき字じ符ふ串くし的てき集合しゅうごう是ぜΣしぐま的てきKleene闭包并被指示しじ为Σしぐま*。依よ据すえΣしぐまⁿ,

$\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表示法ひょうじほう：

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，借か助じょ正せい则表达式来らい帮助文字もじ处理。

算法さんぽう

这是一些字符串处理算法さんぽう，在ざい字じ符ふ串くし上じょう进行不同ふどう的てき处理：

• 字じ符ふ串くし查找算法さんぽう
• 排はい序じょ算法さんぽう
• 正せい则表达式算法さんぽう
• 模も式しき匹ひき配はい

参まいり见

• string —— C++字じ符ふ串くし处理
• string.h —— C语言字じ符ふ串くし处理
• 空そら字じ符ふ串くし
• 正せい则表达式