String

String Algorithms

Writing this stuff more specific for competitive programming.

• Substring: Sequence of consecutive characters in a string. We use the notation s[a...b] to refer to a substring of s that begins at position a and ends at position b. A string of length $n$ has $\frac{n(n+1)}{2}$ substrings.
• Subsequence: sequence of (not necessarily consecutive) characters in a string in their original or
• Prefix: Substring that starts at the beginning of a string. Ex, the prefixes of “ABCD” are “A”, “AB”, “ABC” and “ABCD”,
• Suffix: Substring that ends at the end of a string. Ex: The suffixes of ABCD are D, CD, BCD and ABCD.
• A rotation can be generated by moving the characters of a string one by one from the beginning to the end (or vice versa). For example, the rotations of ABCD are ABCD, BCDA, CDAB and DABC.
• Period is a prefix of a string such that the string can be constructed by repeating the period. The last repetition may be partial and contain only a prefix of the period. For example, the shortest period of ABCABCA is ABC.
• Border: a string that is both a prefix and a suffix of a string. For example, the borders of ABACABA are A, ABA and ABACABA.
• Strings are compared using the lexicographical order (which corresponds to the alphabetical order). It means that x < y if either x 6= y and x is a prefix of y, or there is a position k such that $x[i]=y[i]$ when $i<k$ and $x[k]<y[k]$.

Some important string algorithms topics:

• Trie
• String Hashing
• Z-Algorithm
• Suffix Array

Advanced

• Suffix Tree

You can also use Dynamic Programming to solve the “Edit Distance / Levenshtein Distance” problem.

Related

• Palindrome