i. String Basics and Parsing

Vocabulary and theory the string algorithms rest on (borders and periods, Fine–Wilf, runs), the tool-choice table, brackets, expression parsing, run-length encoding and compression ideas, and string DP. Uses prefixFunction / kmpAutomaton from Prefix Function and Z.

Term	Meaning
substring / subsequence	contiguous block $s[i..j]$ / any positions in order
prefix, suffix (proper: not the whole string)	$s[\mathrm{0..}i]$, $s[i..n)$
border	both a proper prefix and a proper suffix
period $p$	$s[i]=s[i+p]$ for all valid $i$
rotation	$s[i..n)+s[\mathrm{0..}i)$
palindrome	equal to its reverse
run	maximal periodic substring with period $p \le \frac{

A string of length $n$ has $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ substrings (not all distinct) and $2^n$ subsequences. Lexicographic order compares character by character, a proper prefix being smaller; it is not length order ("z" > "abc"). Smallest rotation: Booth or Duval (Lyndon Words); comparing substrings in $O(1)$: hashing + LCP binary search or a suffix array with ranks; $k$-th substring: suffix automaton with path counts.

Border–period duality: $s$ has a border of length $b$ iff it has period $n-b$. So the prefix function answers periodicity: all periods come from the border chain, the smallest is $p=n-\pi [n-1]$, and $s$ is a power of a shorter string iff $p<n$ and $p\mid n$. Fine–Wilf: if $s$ has periods $p$ and $q$ and $|s|\ge p+q-\gcd (p,q)$, it has period $\gcd (p,q)$; the bound is tight. It underlies constant-space matching (Galil–Seiferas, Crochemore–Perrin: Theoretical Algorithms) and the analysis of runs. Runs theorem (Bannai et al. 2015): a string has fewer than $n$ runs, all found in $O(n)$ via Lyndon roots and LCE queries; Main–Lorentz’s $O(n\log n)$ divide and conquer is easier (Runs and Periodicity).

Task	Tool
one pattern in a text	KMP, Z, or hashing
many patterns	Aho–Corasick
compare arbitrary substrings	hashing, or suffix array + LCP
count distinct substrings	suffix automaton $\sum ({\mathrm{len}}_v-{\mathrm{len}}_{\mathrm{link}(v)})$ or $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)-\sum \mathrm{lcp}$ (hashing per length $O(n^2)$, trie of suffixes $O(n^2)$)
longest common substring of two strings	suffix automaton of one, run the other
all palindromic substrings	eertree or Manacher
periods and borders	prefix function
smallest rotation	Booth / Duval
$k$-th substring lexicographically	suffix automaton
LZ factorisation, repetitiveness	suffix automaton (Suffix Automaton)

vector<int> allPeriods(const string& s) {                  // increasing, ends with n
    int n = sz(s); vector<int> res; if (n == 0) return res;
    vector<int> pi = prefixFunction(s);
    for (int b = pi[n - 1]; b > 0; b = pi[b - 1]) res.push_back(n - b);
    res.push_back(n); return res;
}
int smallestPeriod(const string& s) { return sz(s) - prefixFunction(s).back(); }
bool isRepetition(const string& s) { int p = smallestPeriod(s); return p != sz(s) && sz(s) % p == 0; }

Proof: border–period duality, Fine–Wilf, repetitions

Duality: $s[\mathrm{0..}b)=s[n-b..n)$ says $s[i]=s[i+n-b]$ for all $i<b$, which is exactly period $n-b$. Fine–Wilf (induction on $p+q$, $p<q$, $g=\gcd (p,q)$, $n\ge p+q-g$). For $i<n-q$, $s[i]=s[i+q]=s[i+q-p]$, so the prefix $u=s[\mathrm{0..}n-p)$ has period $d=q-p$ as well as $p$. Since $\gcd (p,d)=g$ and $|u|=n-p\ge q-g=p+d-g$, induction gives $u$ period $g$. Because $g\mid d$ we have $g\le q-p$, so $|u|\ge q-g\ge p$: $u$ contains a full period of $s$, hence $s[i]=u[i\mathrm{mod}p]$, and as $g\mid p$ the period $g$ of $u$ carries over to $s$. (If $p=q$ the claim is trivial.) Tightness: aba has periods 2 and 3, length $4-1$, but not period 1. Repetition: if $s=u^k$ with $k\ge 2$ then $|u|$ is a period and $p\le |u|\le n/2$, so $p+|u|\le n$ and Fine–Wilf makes $\gcd (p,|u|)$ a period; minimality gives $p\mid |u|\mid n$. Conversely $p\mid n$, $p<n$ gives $s=(s[\mathrm{0..}p){)}^{n/p}$.

Brackets

vector<int> matchBrackets(const string& s) {               // partner index, -1 if unmatched
    vector<int> mate(sz(s), -1), st;
    for (int i = 0; i < sz(s); i++) {
        if (s[i] == '(') st.push_back(i);
        else if (s[i] == ')' && !st.empty()) mate[i] = st.back(), mate[st.back()] = i, st.pop_back();
    }
    return mate;
}
bool isBalanced(const string& s) { int bal = 0; for (char c : s) { bal += c == '(' ? 1 : -1; if (bal < 0) return false; } return bal == 0; }
pair<vector<int>, vector<int>> bracketForest(const string& s) {   // par[i]: '(' index of the pair directly enclosing pair i
    vector<int> par(sz(s), -1), roots, st, mate = matchBrackets(s);
    for (int i = 0; i < sz(s); i++) {
        if (s[i] == '(' && mate[i] != -1) { if (!st.empty()) par[i] = st.back(); else roots.push_back(i); st.push_back(i); }
        else if (s[i] == ')' && mate[i] != -1) st.pop_back();
    }
    return {par, roots};
}
struct BracketInfo {                                        // segment tree node: longest correct subsequence (CF 380C)
    int matched = 0, open = 0, close = 0;
    static BracketInfo of(char c) { return c == '(' ? BracketInfo{0, 1, 0} : BracketInfo{0, 0, 1}; }
};
BracketInfo operator+(const BracketInfo& a, const BracketInfo& b) {
    int t = min(a.open, b.close);
    return {a.matched + b.matched + t, a.open + b.open - t, a.close + b.close - t};
}

A string is balanced iff all prefix balances are $\ge 0$ and the total is 0; “is $s[l,r)$ balanced” is a range-minimum of prefix balances (lazy segment tree for flips). The longest correct bracket subsequence of a range is $2\cdot$matched of the merged BracketInfo ($O(\log n)$ per query); bracket forests with subtree sizes appear in CF 1821E.

Proof: bracket matching and the merge

The stack holds the unmatched ( so far; a ) is matched with the most recent unmatched (, which is the unique non-crossing matching, and it matches the maximum number of pairs (greedy: any ) that sees an unmatched ( can be matched without hurting later ones). The forest parent of a pair is the innermost pair whose interval contains it, which is the stack top when its ( is pushed. Merge: after greedily matching inside each half, the left half’s unmatched brackets are )...)(...( (closes before opens) and the same for the right; the only new matches pair the left’s unmatched opens with the right’s unmatched closes, $\min ({\text{open}}_L,{\text{close}}_R)$ of them, and this is optimal because the greedy matching of the concatenation is the combination of the halves’ greedy matchings plus these pairs. Checked against brute force subsequence search for short strings.

Expression parsing

Recursive descent with precedence low to high: + -, then * /, then unary + -, then ^ (right-associative: 2^3^2 = 2^(3^2), and -2^2 = -(2^2) = $-4$). Grammar without left recursion: expr := term (('+'|'-') term)*, term := unary (('*'|'/') unary)*, unary := ('+'|'-') unary | power, power := atom ('^' unary)?, atom := number | '(' expr ')'.

struct ExprParser {                                         // O(length); asserts on malformed input
    string s; size_t pos = 0;
    explicit ExprParser(string str) : s(move(str)) {}
    long double parse() { long double v = parseExpr(); assert(peek() == '\0'); return v; }
    void skipSpaces() { while (pos < s.size() && isspace((unsigned char)s[pos])) pos++; }
    char peek() { skipSpaces(); return pos < s.size() ? s[pos] : '\0'; }
    long double parseExpr() { long double v = parseTerm(); for (char c; (c = peek()) == '+' || c == '-';) { pos++; long double t = parseTerm(); v = c == '+' ? v + t : v - t; } return v; }
    long double parseTerm() { long double v = parseUnary(); for (char c; (c = peek()) == '*' || c == '/';) { pos++; long double t = parseUnary(); v = c == '*' ? v * t : v / t; } return v; }
    long double parseUnary() { char c = peek(); if (c == '+') { pos++; return parseUnary(); } if (c == '-') { pos++; return -parseUnary(); } return parsePower(); }
    long double parsePower() { long double b = parseAtom(); if (peek() == '^') { pos++; return powl(b, parseUnary()); } return b; }
    long double parseAtom() {
        if (peek() == '(') { pos++; long double v = parseExpr(); assert(peek() == ')'); pos++; return v; }
        skipSpaces(); size_t st = pos;
        while (pos < s.size() && (isdigit((unsigned char)s[pos]) || s[pos] == '.')) pos++;
        assert(pos > st); return strtold(s.substr(st, pos - st).c_str(), nullptr);
    }
};

Proof: the grammar realises the precedences

Each nonterminal parses a maximal sequence of operands of the next-higher level joined by its own operators, folding left to right, which makes + - and * / left-associative with * binding tighter. power := atom ('^' unary)? recurses to the right through unary, so ^ is right-associative and its right operand may carry a sign, while unary sits below ^, so -2^2 parses as -(2^2). Every rule starts by inspecting one character (peek), so the grammar is LL(1) and the parser runs in linear time. Verified on hand-computed expressions and against a shunting-yard evaluator on random expressions.

Compression ideas

Compression is rarely the goal in contests, but its ideas are constant problem structure.

Idea	Contest form
run-length encoding	$10^9$ characters but $10^5$ runs: solve on the runs; range-assign as an interval map (Chtholly tree, Chtholly Tree); a run of length $L$ contains $\left(\genfrac{}{}{0ex}{}{L+1}{2}\right)$ constant substrings
LZ77 / LZ factorisation	greedy longest earlier-occurring factors; $z$ factors measure repetitiveness; basis of the $O(n)$ runs algorithm; greedy minimises the number of factors; $z\le r$ (BWT runs)
Huffman	merge the two lightest repeatedly (“merge piles, cost = sum”: Greedy); with fixed leaf order use Hu–Tucker / Knuth-optimised interval DP (Knuth Optimization)
Burrows–Wheeler	last column of sorted rotations; from the suffix array; invertible by LF-mapping; FM-index with a wavelet tree (Burrows–Wheeler)
entropy $H=-\sum p_i{\log }_2{p}_i$	lower bound for lossless codes (Huffman within 1 bit, arithmetic coding arbitrarily close); the same counting gives ${\log }_{2}n!=\Omega (n\log n)$ for comparison sorting

vector<pair<char, int>> rle(const string& s) {
    vector<pair<char, int>> r;
    for (int i = 0, j; i < sz(s); i = j) { for (j = i; j < sz(s) && s[j] == s[i]; j++) {} r.push_back({s[i], j - i}); }
    return r;
}
ll constantSubstrings(const string& s) { ll t = 0; for (auto [c, L] : rle(s)) t += (ll)L * (L + 1) / 2; return t; }

String DP

Shape	Problems
two sequences dp[i][j]	LCS; edit distance; longest common substring (reset to 0 on mismatch); regex / wildcard (* = consume or skip); interleaving; distinct-subsequence counts; shortest common supersequence $n+m-\mathrm{LCS}$ (Sequence DP, Hirschberg for linear space)
interval dp[l][r]	longest palindromic subsequence; min insertions to a palindrome $n-\mathrm{LPS}$; remove boxes / Zuma (extra “attached” dimension); counting palindromic subsequences; parenthesisation (Interval DP)
automaton dp[i][state]	strings avoiding one pattern (KMP automaton) or several (Aho–Corasick); distinct substrings / $k$-th substring (suffix automaton); dictionary strings (trie); any regular property (DFA); huge length: matrix power over the automaton

Building block	Precompute
is $s[l..r]$ a palindrome	$O(n^2)$ table, hashes, or Manacher
next occurrence of $c$ at or after $i$	nxt[i][c]: turns subsequence matching into $O(1)$ jumps
$s[l..r]=t[l^{\prime }..r^{\prime }]$, longest common extension	hashing, suffix array + LCP + sparse table

vector<array<int, 26>> nextOccurrence(const string& s) {   // nxt[i][c] = smallest j >= i with s[j] = c, or n
    int n = sz(s); vector<array<int, 26>> nxt(n + 1); nxt[n].fill(n);
    for (int i = n - 1; i >= 0; i--) { nxt[i] = nxt[i + 1]; nxt[i][s[i] - 'a'] = i; }
    return nxt;
}
ll distinctSubsequences(const string& s, ll mod) {          // including the empty one
    int n = sz(s); vector<ll> dp(n + 1, 0); dp[0] = 1; vector<int> last(26, -1);
    for (int i = 0; i < n; i++) {
        dp[i + 1] = 2 * dp[i] % mod;
        int c = s[i] - 'a'; if (last[c] != -1) dp[i + 1] = (dp[i + 1] - dp[last[c]] + mod) % mod;
        last[c] = i;
    }
    return dp[n];
}
ll countAvoiding(const string& pat, int L, int A, ll mod) { // strings of length L over 'a'..'a'+A-1 not containing pat
    int m = sz(pat); auto aut = kmpAutomaton(pat); vector<ll> dp(m, 0); dp[0] = 1;
    for (int i = 0; i < L; i++) {
        vector<ll> nd(m, 0);
        for (int st = 0; st < m; st++) if (dp[st]) for (int c = 0; c < A; c++) { int ns = aut[st][c]; if (ns < m) nd[ns] = (nd[ns] + dp[st]) % mod; }
        dp = nd;
    }
    ll r = 0; for (ll x : dp) r = (r + x) % mod; return r;
}

Proof: distinct subsequences and automaton counting

Distinct subsequences. Let $D_i$ count distinct subsequences of $s[\mathrm{0..}i)$ (with the empty one). Each is either one of them or one of them followed by $s_i$, giving $2D_i$ candidates; the duplicates are exactly the subsequences ending in $c=s_i$ that already ended at the previous occurrence $j$ of $c$, counted by $D_j$ (each such subsequence is a subsequence of $s[\mathrm{0..}j)$ plus $c$). Avoiding a pattern: a string avoids pat iff the KMP automaton, which tracks the longest prefix of pat that is a suffix of the text read, never reaches state $m$; so counting walks of length $L$ in the automaton restricted to states $<m$ counts exactly the avoiding strings. nxt is a suffix minimum, correct by induction from the right. RLE groups maximal runs; a constant substring lies inside exactly one run. All checked by brute force over small alphabets.

Related notes

• Prefix Function and Z
• Runs and Periodicity
• Sequence DP