Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 63 ยท Strings and Games

String Algorithms in Contests

Learn the string toolkit contests rely on: polynomial hashing with a modulus, the Z-function, the prefix function (KMP) and Manacher's palindromes, each tested against brute force.

String problems in contests ask a small number of questions in many disguises: where does this pattern occur, how long is the repeating period, are these two substrings equal, how many palindromes are hidden inside? A naive comparison answers each question in O(n) or worse, so repeated queries on a string of length 200,000 time out. The standard answer is to pre-process the string once and then answer questions in constant time or in a single linear pass.

This lesson teaches four tools. Hashing turns a substring into a number so equality is one comparison. The Z-function and the prefix function (the heart of KMP) describe how a string overlaps with itself. Manacher's algorithm finds every palindrome centered anywhere in O(n). All four are short, and all four are easy to get subtly wrong, so every one of them is checked against a brute force here. If you want the algorithmic background of pattern matching first, read the DSA lessons on strings; here we focus on contest usage. We use the stress-testing loop from stress testing throughout.

flowchart TD
  Q["String question"] --> A{"What do you need?"}
  A -->|"compare many substrings"| H["Hashing"]
  A -->|"match against one fixed pattern"| Z["Z-function or prefix function"]
  A -->|"periods and borders"| P["Prefix function"]
  A -->|"palindromic substrings"| M["Manacher"]

Pick the tool from the question you are asked.

Polynomial hashing

Treat a string as a number written in some base: the hash of s[0..n) is s[0]*B^(n-1) + s[1]*B^(n-2) + ... + s[n-1], taken modulo a big prime M. Compute prefix hashes once, h[i+1] = (h[i]*B + code(s[i])) % M, and the hash of any substring s[l..r) falls out in O(1):

hash(l, r) = (h[r] - h[l] * B^(r-l)) % M

Equal substrings always have equal hashes. The reverse is only probably true: two different strings can collide. The smaller the modulus, the more often that happens. A modulus near 10^9 is borderline when you compare millions of pairs, because collisions become likely (the birthday effect). Python makes the fix cheap: use the Mersenne prime 2^61 - 1, which keeps collisions practically out of reach, and pick the base freely. Python's big integers handle the multiplication without overflow.

Python Substring equality and occurrence counting with hashes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Now see why the modulus matters. This TryIt hashes with a deliberately tiny modulus and searches for two different strings with the same hash.

Python A collision with a tiny modulus

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On sites where hacking is allowed (Codeforces, for instance), a fixed modulus and base can be attacked. Use a large modulus, and pick the base at random when your program starts (random.randrange(256, MOD - 1)). Do not hash with a modulus below about 10^9 when comparing many substrings, and use double hashing or 2^61 - 1 for safety. Hashing is a probabilistic tool: when you need a guaranteed answer, use the Z-function or the prefix function.

The Z-function

For a string s, z[i] is the length of the longest common prefix of s and the suffix starting at i. By convention z[0] = n. The algorithm keeps the rightmost matched window [l, r); for a new index i inside the window, the answer is at least min(r - i, z[i - l]) because the window already copies the start of the string. It then extends by direct comparison. The extension only moves r forward, so the total work is O(n).

To find a pattern P in a text T, compute the Z-array of P + "#" + T, where # is a character that occurs in neither string. Every position with z >= len(P) is an occurrence.

The prefix function

pi[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of it. That quantity is called the longest border. To compute pi[i], start from the previous border k = pi[i-1] and, while the next character does not match, fall back with k = pi[k-1]. If s[i] == s[k], the border grows by one. Each fallback pays for an earlier increase, so the total is O(n). This fallback rule is exactly what KMP search uses.

Two classic consequences matter in contests:

  • Smallest period. If p = n - pi[n-1] divides n, the string is n/p copies of its first p characters; otherwise the string is not periodic and the answer is n.
  • All borders. Follow the chain pi[n-1], pi[pi[n-1]-1], ... down to 0. These are all lengths where a prefix equals a suffix.
Python Z-function and prefix function checked by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The overlapping matches at positions 0, 2 and 4 show that both algorithms handle overlap correctly, which is where a hand-written find loop usually fails.

Z-function and prefix function carry the same information, in different forms. Z talks about the start of the string versus each position, which suits "match a pattern at each position". The prefix function talks about borders ending at each position, which suits periods and automaton-style problems. Learn both; pick whichever makes the problem statement read naturally.

Manacher's algorithm for palindromes

Expanding around every center takes O(n^2) in the worst case (a string of all a). Manacher's algorithm uses the same mirroring idea as the Z-function: if a palindrome is centered at c and reaches to r, then a position i inside it mirrors to 2c - i, and the palindrome radius there gives a lower bound for i.

The standard trick is to insert a separator between characters, turning abba into #a#b#b#a#, so even-length and odd-length palindromes are both centered on a single position. The radius d[i] on the transformed string equals the length of the longest palindrome centered there in the original. The number of palindromic substrings is the sum of (d[i] + 1) // 2 over all centers, because a center with radius d contributes that many palindromes.

Python Manacher: longest and total palindromes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which tool for which problem

Task Tool Time
Are s[a..b) and s[c..d) equal? (many queries) Hash O(n) build, O(1) per query
Find a pattern in a text Z-function or prefix function O(n + m)
Smallest repeating period, all borders Prefix function O(n)
Longest or number of palindromic substrings Manacher O(n)
Longest repeated substring, lexicographic questions Suffix structures (beyond this lesson) O(n log n)

Remember Python's speed limits from Python for contests: a pure-Python loop handles about 10^6 characters comfortably, so for strings near 10^6 prefer functions that avoid nested Python loops, or use the built-in str.find and str.count when they are enough. They are fast, written in C, and fine for a single search; the algorithms above matter when you need many answers from the same string.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is a modulus such as 1000 dangerous for string hashing?

    With few possible hash values, collisions are common. A large modulus such as 2^61 - 1 makes them extremely unlikely.
  2. 2. What does z[i] mean in the Z-function of a string s?

    z[i] compares the whole string with its suffix starting at position i and counts how many leading characters match.
  3. 3. The prefix function of a string of length 9 ends with pi[8] = 6. What is the smallest period of the string?

    The candidate period is n - pi[n-1] = 3. Since 3 divides 9, the string is three copies of its first three characters.
  4. 4. Why do we insert a separator character in Manacher's algorithm?

    An even-length palindrome has its center between two letters. A separator gives it a center position of its own.
  5. 5. Which tool gives a guaranteed (not probabilistic) answer to 'where does pattern P occur in text T'?

    The Z-function compares real characters, so it never reports a false match. Hashing can, with tiny probability.

Summary

  • Prefix hashes answer "are these substrings equal" in O(1); use a large modulus (such as 2^61 - 1) and a random base to make collisions practically impossible.
  • The Z-function and the prefix function process a string in O(n) and find all pattern occurrences without hashing.
  • n - pi[n-1] gives the smallest period when it divides n, and following pi links lists all borders.
  • Manacher's algorithm finds every palindrome center in O(n) by mirroring inside the current palindrome, using separators to unify even and odd lengths.
  • Check every string algorithm against a brute force on tiny random strings over a two-letter alphabet.

Next: Game Theory