Занятие 2. Параллель B – Строки 1

Main Ideas

1. Prefix Function and Borders

A border of a string is a string that is both a prefix and a suffix. It must be a proper border, meaning it cannot be the entire string.

The prefix function (\pi[i]) gives the length of the longest proper border of the prefix ending at position (i).

A straightforward method checks every possible border length and compares the corresponding characters. Computing the function for every prefix this way can take (O(n^3)) time.

A first improvement uses the fact that when a character is appended, the longest border can grow by at most one. This reduces the work to (O(n^2)), but still repeats many character comparisons.

The efficient method avoids rechecking characters already known to match:

1. For each new position, start by trying the previous prefix-function value plus one.
2. If the next characters do not match, follow the prefix-function links to shorter candidate borders.
3. Stop at the first candidate that can be extended, or at zero.

Although the fallback loop can move backward many times, each successful increase is by at most one. Therefore, the total number of increases and decreases is linear. With only constant work per candidate, the full prefix-function algorithm runs in (O(n)) time.

2. KMP Pattern Search

To find every occurrence of pattern (S) in text (T):

1. Concatenate (S), a separator character absent from both strings, and (T): S + separator + T.
2. Compute the prefix function of the concatenated string.
3. Whenever the prefix-function value reaches (|S|), the pattern ends at that position in the text.
4. Convert that ending position into the corresponding starting position.

The separator prevents matches from extending across the pattern–text boundary. The method takes (O(|S|+|T|)) time.

The prefix function is also useful when text arrives one character at a time. The next value can be computed using the existing prefix-function state without storing or reprocessing the entire text, which can reduce memory use.

3. Z-Function

The Z-function at position (i) is the length of the longest substring starting at (i) that matches a prefix of the whole string.

A naive approach compares forward from every position and takes (O(n^2)) time in the worst case. The linear-time method maintains the rightmost segment ([L,R)) already known to match the string’s prefix:

1. If the current position is inside that segment, initialize its Z-value using the corresponding value from the prefix.
2. Limit the initial value to the known segment’s right boundary.
3. Compare characters only when extending beyond that boundary.
4. If the match extends farther right, update ([L,R)).

The right boundary advances at most (n) times, giving (O(n)) total time.

Pattern search can also use the Z-function on S + separator + T: positions with Z-value (|S|) mark occurrences. The separator makes the test direct.

When to use which: The Z-function is a convenient linear-time string tool when the whole string is known. The prefix function is especially useful for incremental processing and for building the KMP automaton.

4. Prefix-Function Automaton

The lecturer briefly introduces a KMP-based automaton for a fixed pattern. Its states represent how many pattern characters currently match a suffix of the processed text. Each incoming character causes a transition to another state, possibly falling back along borders.

Precomputing transitions allows the text to be processed incrementally, and saved states can support limited rollback.

5. Tries for Storing Words

A trie represents words as paths from a root, with edges labeled by characters. Each node stores whether a word ends there (terminal status) and transitions to child nodes for the alphabet’s characters.

• Insert: Follow the word’s characters, create missing nodes, then mark the final node terminal.
• Search: Follow the characters. Fail if a transition is missing; otherwise, return whether the final node is terminal.
• Delete: Follow the same path and unset terminal status. Nodes do not need to be removed if they may still serve as prefixes for other words.

To count how many stored words have a given prefix, store a subtree count at each node. Increment it along the insertion path and decrement it along the deletion path. After following the query prefix, the count gives the answer.

A fixed child array gives fast transitions but can use substantial memory. Alternatives include vectors, ordered maps, and hash maps, with different trade-offs in memory usage and lookup speed.

6. Binary Trie for Maximum XOR

For a set of integers represented as fixed-length binary strings:

1. Insert each number’s bits into a trie with two possible edges, 0 and 1.
2. To find the number that maximizes XOR with a query (x), inspect bits from most significant to least significant.
3. At each bit, prefer the branch opposite to (x)’s bit, because that makes the current XOR bit 1.
4. If that branch is unavailable, take the matching branch.

This greedily maximizes the XOR value because more significant bits matter more. Counts can be added to nodes if numbers must support insertion and deletion.

Graph and Contest-Problem Discussion

The latter part reviews graph problems from a contest:

• A: Implement an algorithm covered in the lecture; the lecturer does not revisit its details.
• B — Validate a topological ordering: Record each vertex’s position in the proposed order. Check every directed edge (u \to v); the order is valid exactly when position[u] < position[v] for every edge.
• C — Strongly connected components: Use the SCC method discussed earlier in the lecture.
• D — Shortest path in a weighted DAG: Topologically sort the graph and use dynamic programming. For each edge (v \to u), relax the distance using dist[v] + weight(v, u), processing vertices in topological order.
• E — Sum of distances over all tree paths: For each edge of weight (w), removing it splits the tree into components of sizes (C_1) and (C_2). The edge lies on (C_1C_2) paths between unordered pairs, so its contribution is (C_1C_2w). For an ordered-pair sum, multiply by two. Subtree sizes from a DFS provide the component sizes.

• F — Sum of distances from every tree vertex: First compute, with a rooted-tree DFS, each subtree’s size and the sum of distances from its root to vertices in that subtree. Then reroot the result across each edge. If (v) is a child of (u), the all-vertices distance sum changes by [ \text{answer}[v] = \text{answer}[u]

  + w(u,v)\bigl(n-2\,\text{size}[v]\bigr). ]

• G — Divisibility constraints: Make a directed graph with an edge for each divisibility condition and find its strongly connected components. Variables in the same component must have equal absolute values. Different components can be assigned distinct magnitudes. A nontrivial component can contribute two distinct signed values; a singleton contributes one. Thus, the maximum number of distinct values is (2K-s), where (K) is the number of SCCs and (s) is the number of singleton SCCs.

• H — Dependencies for producing a part: Find all tasks reachable from part 1 using DFS. A topological ordering gives a valid production order, and summing the times of the reachable tasks gives the total time.
• I — Minimize the maximum weight on a walk of (k) vertices: Binary-search a threshold (x), keeping only vertices whose weights are at most (x). If the remaining graph contains a directed cycle, a walk of arbitrary length can repeat it. Otherwise, the graph is a DAG; find its longest path and check whether it has at least (k) vertices. This gives a feasibility test for the binary search.
• J — Choose the lexicographically optimal topological order: To maximize the final vertex first, repeatedly remove the largest-numbered sink (a vertex with no outgoing edges). Update the outgoing-edge counts of its predecessors and add any newly available sinks to the candidate set. The removal sequence determines the order from last to first, so reverse it to obtain the topological order.
• K: The lecture ends just as the instructor is about to discuss this problem; no solution is included in the subtitles.

Speakers and Sources

• Main lecturer: An unnamed instructor who presents the string algorithms, trie material, binary trie, and contest-problem solutions.
• Students and attendees: Ask questions and make brief comments, including through the chat. They are not individually identified in the subtitles.
• People mentioned but not clearly identified as speakers: Mikhail Perveev is mentioned in connection with an alternative name for the Z-function. Artyom, Tanya, and Timofey are also mentioned during classroom logistics or as participants.
• External sources: None are clearly featured; the material is presented as a classroom lecture.