String algorithms

The problem is as plain as it gets: in a text haystack of length n, find the first position where a pattern needle of length m occurs. The most natural idea is to line the pattern up with every start position and compare character by character. If the characters match, move one step right. If they do not, move to the next start position. That is naive matching, also called brute force.

It is correct, but slow. Where does the time go? Watch this run in slow motion: find abab inside abaabab. Keep your eye on the pointer i. On every mismatch it is pulled back to the position right after the current start, and everything the earlier successful comparisons established is lost.

How bad can the worst case get? Take the text aaaa…aab and the pattern aaab. Every start position has to be compared all the way to the last character before it fails, so the number of comparisons is about n×m. That is the O(n·m) of naive matching. The problem is not that comparing characters is slow. The problem is that every failure starts over from nothing, even though a long prefix was just confirmed to match.

All of KMP fits into one array, called the prefix function. In code it is usually named next or fail, and in papers it is written π. Its definition is one sentence, but every word in it matters.

An example: the substring abab. Its proper prefixes are a / ab / aba, and its proper suffixes are b / ab / bab. The longest one that appears in both lists is ab, length 2, so the last entry of next for abab is 2.

Why does this number let the text pointer i stay where it is? Picture the moment of failure: the first j characters of the pattern have matched the text, and character j + 1 does not. Those j matched characters are both a part of the text and exactly the pattern prefix pattern[0..j−1]. Suppose that prefix has an equal proper prefix and suffix of length k. Then its last k characters are the same as its first k characters. So the pattern can slide right until its first k characters sit where those last k characters were. They are equal by construction, so there is nothing to compare again, and i does not have to move back.

How is the whole table computed? Here is the neatest step in KMP: building the next array is itself a KMP search, with the pattern searched inside the pattern. This is called self-matching.

The method is incremental. Assume next[0..i−1] is already known and compute next[i]. Keep a value j meaning "how long the equal prefix and suffix reached at the previous position", which starts at j = next[i−1]. Then compare the new character pattern[i] with pattern[j]:

• They match (pattern[i] == pattern[j]): the equal prefix and suffix both grow by one, so j++ and next[i] = j.
• They do not match (pattern[i] ≠ pattern[j]): the current prefix cannot be extended, so fall back with j = next[j−1] — move to a shorter prefix that may still continue, and try again, until it matches or j reaches 0.

The two-row table below animates it. The top row is the pattern abababca and the bottom row is the next value filled in cell by cell. The solid blue cell is the prefix character pattern[j] being compared, and the dashed blue cells are the prefix matched so far. Pay special attention to i=6, the character c, where the fallback happens several times in a row:

Understanding the fallback chain at i=6 is half of understanding KMP. c is compared with pattern[4]=a and fails; j falls back to next[3]=2 and c is compared with pattern[2]=a, which fails; j falls back to next[1]=0 and c is compared with pattern[0]=a, which fails again, so next[6]=0. Each jump along the next chain replaces the candidate prefix with a shorter one, and that is exactly how known information is reused instead of recomputed. The construction code and the matching code are almost the same:

With the next table in hand, the matching loop looks almost identical to the construction loop. Only the comparison changes, from pattern against pattern to pattern against text. Keep a value j meaning how many pattern characters currently match: compare haystack[i] with pattern[j], and on a match do j++, on a mismatch do j = next[j−1]. i only ever increases. When j reaches m, the pattern has been found. Here is the same pair abaabab and abab again, this time with KMP:

The problem (LC 28): return the index of the first occurrence of needle in haystack, or −1 if there is none. Naive: shown above, O(n·m). Why it can be improved: on a mismatch, the suffix that already matched contains a part that is equal to a prefix. The next table measures that in advance, so a mismatch becomes a jump instead of a restart. Solution: build next in O(m), then scan the text in O(n):

KMP gets its speed from preprocessing the pattern. There is a completely different route: Rabin-Karp, which hashes a substring of length m into a single number, like a fingerprint. To test whether two substrings are equal, compare their hashes first. Different hashes mean the substrings are definitely different, so that position can be skipped. Equal hashes mean the characters have to be compared.

If each window's hash were computed from scratch, the total would still be O(n·m) and nothing would be gained. The point is the rolling hash: when the window moves one step right, the hash updates in O(1) — subtract the contribution of the character that leaves, multiply the rest by the base, and add the character that enters. Watch it:

Treat the substring as a polynomial in the base (a polynomial rolling hash): hash = c₀·baseᵐ⁻¹ + c₁·baseᵐ⁻² + … + cₘ₋₁. Here cᵢ is the character code, which may be larger than the base. That is allowed, because this is a hash function and not a positional number system. When the window moves right, drop the highest term, shift the rest up by one power (multiply by the base), and add the new character in the lowest position, so the update is O(1). Everything is taken modulo a large prime to keep the numbers in range. A base at least as large as the alphabet is normal: 26 or 31 for 26 lowercase letters, and something larger such as 131 when the text can contain any ASCII character.

The problem (LC 459): decide whether a string s can be built by repeating one of its substrings two or more times. For example abab = ab×2 → true, and aba → false. Naive: try every candidate period length d that divides n and verify each one, which is about O(n²). Why it can be improved: a repeating structure leaves a clear mark in the next array.

Let n = s.length and k = next[n−1], the length of the longest equal proper prefix and suffix of the whole string. The conclusion:

Check it on two more examples. abcabcabc: n=9, the last next value is k=6, the candidate period length is 9 − 6 = 3, and 9 % 3 == 0 with 6 > 0 → true, with period abc. Now aba: n=3, k=1, the candidate length is 2, but 3 % 2 ≠ 0 → false. The test is exact:

A different kind of structure: a palindrome reads the same forwards and backwards, such as aba or abba. The problem (LC 5): find the longest palindromic substring of a string. Naive: take all O(n²) substrings and check each one, at O(n) per check, for O(n³) in total. Why it can be improved: a palindrome is symmetric around its center. Instead of choosing the two ends and then checking, choose the center and expand outwards, which keeps the symmetry true by construction.

The DataData two-pointer chapter introduced the intuition for expanding from a center; this is a review that then connects to Manacher. The one thing to watch is that palindromes have odd and even lengths: the center of aba is a character, while the center of abba is the gap between two characters. So there are 2n−1 centers to try: n characters and n−1 gaps. Watch:

There is a classic off-by-one in the implementation. When the expansion loop exits, the left and right pointers have each moved one step too far and stand on the pair that did not match. So the palindrome is the range [l+1, r−1] and its length is r−l−1. Keep that in mind and the code follows:

Not every string problem is about matching. The other large group is parsing and mapping, where the test is not an algorithmic trick but translating a set of boundary rules into code without missing any and without duplicating any. Interviewers like these problems because they are close to real work: turning an unclear requirement into exact logic.

LC 205 isomorphic strings: can s become t by replacing characters one for one? egg → add works; foo → bar does not, because o would have to become both a and r. The key is a mapping in both directions: s → t must be consistent and t → s must be consistent too. Checking only one direction accepts the case where two different characters land on the same target:

LC 8 string to integer (atoi): parse text that may contain leading spaces, a sign, and invalid characters into a 32-bit integer. There is no algorithm here, only rules. Writing them as a state machine makes it clear: (1) skip leading spaces, (2) read one optional sign, (3) read digits, (4) stop at the first non-digit, (5) clamp to [INT_MIN, INT_MAX] on overflow: