跳转至

字符串

一个 字符串 \(S\) 是将 \(n\) 个字符顺次排列形成的序列,\(n\) 称为 \(S\) 的长度,表示为 \(|S|\)

如果字符串下标从 \(1\) 开始计算,\(S\) 的第 \(i\) 个字符表示为 \(S[i]\)

如果字符串下标从 \(0\) 开始计算,\(S\) 的第 \(i\) 个字符表示为 \(S[i-1]\)

子串

字符串 \(S\)子串 \(S[i..j],i≤j\),表示 \(S\) 串中从 \(i\)\(j\) 这一段,也就是顺次排列 \(S[i],S[i+1],\ldots,S[j]\) 形成的字符串。

有时也会用 \(S[i..j]\)\(i>j\) 来表示空串。

子序列

字符串 \(S\)子序列 是从 \(S\) 中将若干元素提取出来并不改变相对位置形成的序列,即 \(S[p_1],S[p_2],\ldots,S[p_k]\)\(1\le p_1< p_2<\cdots< p_k\le|S|\)

后缀

后缀 是指从某个位置 \(i\) 开始到整个串末尾结束的一个特殊子串。字符串 \(S\) 的从 \(i\) 开头的后缀表示为 \(\textit{Suffix(S,i)}\),也就是 \(\textit{Suffix(S,i)}=S[i..|S|-1]\)

真后缀 指除了 \(S\) 本身的 \(S\) 的后缀。

举例来说,字符串 abcabcd 的所有后缀为 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd},而它的真后缀为 {d, cd, bcd, abcd, cabcd, bcabcd}

前缀

前缀 是指从串首开始到某个位置 \(i\) 结束的一个特殊子串。字符串 \(S\) 的以 \(i\) 结尾的前缀表示为 \(\textit{Prefix(S,i)}\),也就是 \(\textit{Prefix(S,i)}=S[0..i]\)

真前缀 指除了 \(S\) 本身的 \(S\) 的前缀。

举例来说,字符串 abcabcd 的所有前缀为 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabc}

字典序

以第 \(i\) 个字符作为第 \(i\) 关键字进行大小比较,空字符小于字符集内任何字符(即:\(a< aa\))。

回文串

回文串 是正着写和倒着写相同的字符串,即满足 \(\forall 1\le i\le|s|, s[i]=s[|s|+1-i]\)\(s\)

字符串基础 - OI Wiki (oi-wiki.org)