Skip to content

String Basics

Definition

Character Set

A character set \(\Sigma\) is a set that establishes a total order relation, meaning that any two distinct elements \(\alpha\) and \(\beta\) in \(\Sigma\) can be compared in size, either \(\alpha<\beta\) or \(\beta<\alpha\). Elements in the character set \(\Sigma\) are called characters.

String

A string \(S\) is a sequence formed by arranging \(n\) characters in order, where \(n\) is called the length of \(S\), denoted as \(|S|\).

If string indexing starts from \(1\), the \(i\)-th character of \(S\) is denoted as \(S[i]\);

If string indexing starts from \(0\), the \(i\)-th character of \(S\) is denoted as \(S[i-1]\).

Substring

The substring \(S[i..j]\), \(i \le j\), of a string \(S\) represents the segment from \(i\) to \(j\) in \(S\), i.e., the string formed by sequentially arranging \(S[i], S[i+1], \ldots, S[j]\).

Sometimes \(S[i..j]\), \(i > j\), is used to denote an empty string.

Subsequence

A subsequence of a string \(S\) is a sequence formed by extracting several elements from \(S\) without changing their relative positions, i.e., \(S[p_1], S[p_2], \ldots, S[p_k]\), where \(1 \le p_1 < p_2 < \cdots < p_k \le |S|\).

Suffix

A suffix is a special substring that starts from a certain position \(i\) and extends to the end of the entire string. The suffix of string \(S\) starting at \(i\) is denoted as \(\textit{Suffix(S,i)}\), i.e., \(\textit{Suffix(S,i)} = S[i..|S|-1]\).

A proper suffix refers to any suffix of \(S\) other than \(S\) itself.

For example, all suffixes of the string abcabcd are {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd}, while its proper suffixes are {d, cd, bcd, abcd, cabcd, bcabcd}.

Prefix

A prefix is a special substring that starts from the beginning of the string and ends at a certain position \(i\). The prefix of string \(S\) ending at \(i\) is denoted as \(\textit{Prefix(S,i)}\), i.e., \(\textit{Prefix(S,i)} = S[0..i]\).

A proper prefix refers to any prefix of \(S\) other than \(S\) itself.

For example, all prefixes of the string abcabcd are {a, ab, abc, abca, abcab, abcabc, abcabcd}, while its proper prefixes are {a, ab, abc, abca, abcab, abcabc}.

Lexicographical Order

Comparison is performed using the \(i\)-th character as the \(i\)-th key, with the empty character being smaller than any character in the character set (i.e., \(a < aa\)).

Palindrome

A palindrome is a string that reads the same forwards and backwards, i.e., a string \(s\) satisfying \(\forall 1 \le i \le |s|, s[i] = s[|s|+1-i]\).

Hamming Distance

The Hamming distance is the distance between two strings of equal length, representing the number of positions at which the corresponding characters differ.

We can simply consider performing an XOR operation on the two strings; the number of \(1\)s in the result is the Hamming distance between the two strings.

Storage of Strings

  • Use a char array for storage, with the null character \0 indicating the end of the string (C-style string).
  • Use the string class provided by the C++ standard library.
  • String constants can be represented using string literals (strings enclosed in double quotes).
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用