字

字是把字母表中的原子按有限顺序排成的一条序列。把它形式化为位置到符号的函数，可以精确谈长度、切片和连接，而不依赖某种具体字符串存储。顺序与重数都重要：01、10 和 001 是三个不同的字。空字虽然没有符号，却是连接运算的单位元，因此不能把它当作“什么都没有而无需纳入集合”。

在 $\mathrm{\Sigma }=\{a,b\}$ 上，$w=abba$ 的长度为 $4$，ab 是前缀，ba 是后缀，第二至第三位置形成子串 bb。空字满足 $|\epsilon |=0$，并属于每个 ${\mathrm{\Sigma }}^{\ast }$。

在 abba 中，aa 是选取第 $1,4$ 位得到的子序列，却不是子串，因为两个 a 不相邻。子串必须保留一整段位置，子序列只保留先后关系；搜索连续片段与检查删除后能否得到目标字因此是不同问题。取零个位置得到空字，所以空字既是每个字的子串，也是子序列。

回文与回文半径理路回文与回文半径Palindrome · Palindromic radius · 回文子串用反转不变定义回文，以奇偶两类中心的最大半径压缩全部回文出现，并区分出现区间、不同内容与分解目标。专门分析正反读取一致的连续子串。它保留本段的连续性要求：abca 中的 aba 可以作为子序列，却不能作为回文子串的一次出现；相同回文内容在不同区间出现时也要分别计数。

边界是空字与空语言的区别：$\epsilon$ 是一个字，而 $\varnothing$ 是不含任何字的语言；$\{\epsilon \}$ 则是恰含一个长度零字的语言。无限符号序列不属于 ${\mathrm{\Sigma }}^{\ast }$，需要 ω-word 等不同模型。

$\epsilon$ 通常不属于字母表 $\mathrm{\Sigma }$，除非有人刻意把一个同名印刷符号作为普通元素加入；作为空序列的 $\epsilon$ 长度仍为零。字也不能定义成字母表的有限子集，因为集合表示会丢失顺序与重复次数。

字是形式语言理路形式语言Formal language · Language over an alphabet固定字母表上有限字的任意集合，是识别器、文法与判定问题共同描述的对象。的元素，也是有限状态自动机理路有限状态自动机Finite-state automaton · Finite automaton用有限个控制状态概括已读前缀，并沿带输入标号的转移识别有限字的模型家族。与图灵机读取的有限输入。字符串连接理路字符串连接String concatenation把第二个字的符号接在第一个字之后形成的新字及相应结合运算。把字组成自由幺半群，长度给出与连接相容的自然数分级。

前缀、后缀和子串结构支撑字符串匹配、词法分析、编码理论与 Myhill–Nerode 区分后缀的定义。形式语言里的 word 是字母序列；Word-RAM 的 machine word 则是固定 $w$-bit 运算单元，两者不能因英文同名而混用。

字符串周期与 border理路字符串的周期与 borderPeriod of a word · Border of a word · 字符串周期 · 前后缀重合用错位后仍相等的位置定义有限字符串的周期，并把长度 p 的周期与长度 n-p 的前后缀重合一一对应。把位置重合写成可检验的等式，本原根理路本原词与唯一重复根Primitive word · Primitive root of a word · 本原字 · 字符串本原根不能写成更短非空词的二次或更高整数幂的词称为本原词；每个非空词都能唯一写成本原根的正整数幂。再区分截断重复与完整整数幂。词的共轭理路词的共轭与循环移位Conjugate words · Cyclic rotation of a word · Circular string · 词的旋转等价把词切为 uv 再连接成 vu 定义旋转等价；本原根的长度决定不同旋转的个数和相同旋转起点的间隔。允许改变起点而保留绕行方向；在字符全序下，Lyndon 词理路Lyndon 词Lyndon word · Lyndon字 · 林登词在固定字母序下严格小于每个非零循环移位的非空词，等价于严格小于每个非空真后缀的词。和CFL 分解理路Chen–Fox–Lyndon 唯一分解Chen–Fox–Lyndon theorem · Lyndon factorization · CFL factorization · Lyndon唯一分解每个有限词都能唯一分解成按字典序非增排列的非空 Lyndon 因子；最末因子由全词最小非空后缀唯一确定。分别给出本原循环类的唯一代表与任意词的唯一下降分块。

压缩索引进一步把字符串视作 bit 串与可导航序列：rank/select理路Rank 与 Select 查询Rank and select在位串上计算前缀频数或定位第 j 次出现，并固定端点和索引约定。在位位置上计数与定位，简洁位向量理路简洁位向量succinct bit vector · rank-select bit vector以 n+o(n) 位表示静态位串，并在 Word-RAM 上常数时间支持 rank 与 select。按 bit 报空间，FM-index理路FM-indexFM-index · Full-text minute-space index在压缩 BWT 上提供 rank 支持，以反向搜索完成模式计数，并通过采样后缀数组和逆后缀数组实现定位与文本提取。从 BWT 表示支持模式搜索。这些页面都保留字符边界、字母表编码和机器字打包三个层次。

同一个字在亚线性模型中还会被分配不同的可见性。Indexing理路Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。让 Alice 看见整个 bit 字而 Bob 只持索引，输出虽只有一位，通信仍可能线性；位查询模型理路查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。则让单个算法按位置读取隐藏字，并把读取次数作为成本。性质距离理路到性质的距离Distance to property · Distance from a property以到性质成员的距离下确界衡量接近程度，并明确归一化、闭性与测试承诺。常把两个等长字的 Hamming 差异除以长度，但测试器还需声明可查询坐标和 far 阈值。字的集合论定义没有改变，改变的是谁看见哪些符号以及访问一次如何计费。

当符号集合还带全序时，RSK词插入理路RSK 词插入与逆恢复Robinson-Schensted word correspondence · RSK word insertion · Schensted row insertion · 行插入与记录表固定严格大于的行插入与严格小于的逆撞规则，证明有限词和同形表对双射、内容保持及第一行最长弱递增长度，再计算指定形状的词纤维。给有限字另一种可逆表示：同形的插入表P和标准记录表Q。P保留符号重数，Q记录每次新增角格，两者合起来才能逆恢复所有位置。词$132$和$312$具有同一P而Q不同，说明只保存整理后的值会丢失顺序。只取第一行还可求最长弱递增子序列的长度，但这种更小输出也不再承诺恢复原字。