String Basics

Definition

Character Set

A character set $\Sigma$ is a set equipped with a total order, which means that any two distinct elements $\alpha$ and $\beta$ in $\Sigma$ can be compared: either $\alpha<\beta$ or $\beta<\alpha$. The elements of the character set $\Sigma$ are called characters.

String

A string $S$ is a sequence formed by arranging $n$ characters in order. $n$ is called the length of $S$, denoted by $|S|$.

If string indices start at $1$, the $i$-th character of $S$ is denoted by $S[i]$;

if string indices start at $0$, the $i$-th character of $S$ is denoted by $S[i-1]$.

Substring

The substring $S[i..j]，i≤j$ of string $S$ denotes the segment from $i$ to $j$ in $S$, namely the string formed by arranging $S[i],S[i+1],\ldots,S[j]$ in order.

Sometimes $S[i..j]$, $i>j$, is also used to denote the empty string.

Subsequence

A subsequence of string $S$ is a sequence formed by extracting some elements from $S$ without changing their relative positions, namely $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 at some position $i$ and ends at the end of the entire string. The suffix of string $S$ starting at $i$ is denoted by $\textit{Suffix(S,i)}$, namely $\textit{Suffix(S,i)}=S[i..|S|-1]$.

A proper suffix is a suffix of $S$ other than $S$ itself.

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

Prefix

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

A proper prefix is a prefix of $S$ other than $S$ itself.

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

Lexicographic Order

Compare strings by using the $i$-th character as the $i$-th keyword. An empty character is smaller than every character in the character set (that is, $a< aa$).

Palindrome

A palindrome is a string that is the same when written forwards and backwards, that is, an $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; it is the number of positions at which the corresponding characters of the two strings differ.

It can be simply understood as the number of $1$ bits obtained by XORing the two strings.

String Storage

• Store strings in a char array, using the null character \0 to mark the end of the string (a C-style string).
• Use the string class provided by the C++ standard library.
• String constants can be represented by string literals (strings enclosed in double quotation marks).