子串

在形式语言理论和计算机科学中，子串是一个字符串中连续的字符序列。例如，thebestof是Itwasthebestoftimes的一个子串。相反，Itwastimes是Itwasthebestoftimes的一个子序列，但不是一个子串。前缀和后缀是子串的特殊情况。一个字符串的前缀S{displaystyleS}是一个字符串S的前缀。的一个子串，是S{displaystyleS}的一个子串。的子串，它出现在S{displaystyleS}的开头的子串。的开头；同样地，一个字符串的后缀S{displaystyleS}的后缀是出现在S{displaystyleS}末尾的子串。的后缀是出现在S的末尾的一个子串。S{displaystyleS}的末尾的一个子串。子串A字符串一个字符串的子串是该字符串的后缀的前缀，也可以说是前缀的后缀；例如，nan是nana的前缀，而nana又是banana的后缀。如果u{displaystyleu}是的一个子串t{displaystylet}的子串，它也是一个子序列。的子串，它也是一个子序列，这是一个更普遍的概念。一个给定的模式在一个给定的字符串中的出现可以用一个字符串搜索算法找到。在数学文献中，子串也被称为子字（在美国）或因子（在欧洲），找到等于两个或多个字符串的最长的字符串被称为最长的公共子串问题。前缀一个字符串.字符串的适当前缀不等于字符串本身；此外，一些资料还限制适当前缀必须是非空的。前缀可以被看作是子串的一个特例。例如。字符串ban等于字符串banana的一个前缀（以及子串和子序列）。

.一个字符串的适当后缀不等于该字符串本身。一个更有限的解释是，它也不是空的。[1]后缀可以被看作是子串的一个特例。例子。字符串nana等于字符串banana的一个后缀（以及子串和子序列）。banana||||nana字符串的后缀树是一个表示所有后缀的trie数据结构。后缀树在字符串算法中有着大量的应用。后缀数组是这种数据结构的简化版本，它以字母排序的方式列出后缀的起始位置；它有许多相同的应用。

边框是同一个字符串的后缀和前缀，例如，bab是babab的边框（也是baboon吃kebab的边框）。超弦一个有限集合的超弦{text{efabccla}的所有成员连接起来。的所有成员，以任意的顺序，总是可以得到一个琐碎的超弦的P{displaystyleP}的琐碎超弦。.寻找长度尽可能小的超弦是一个更有趣的问题。一个包含指定字符集的所有可能的排列组合的字符串被称为超级排列组合。