INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE
01
00/15
01 / COVER MODULE 29 · STRINGS
INVARIANT · MODULE 29 · ADVANCED STRINGS
NEVER COMPARE THE SAME LETTER TWICE

The plain way to match strings compares a letter, forgets it, and compares it again. Each move here keeps what a comparison already proved: the longest border, how far a suffix matches the start, the code of a window, the rightmost palindrome, the rotation that lost. Nine moves, fifteen problems.

15Problems
5Families
9Units
9Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

THE PREFIX FUNCTION · 04
SEARCH WITH IT · 03
THE Z FUNCTION · 02
ROLLING CODES AND HASHES · 04
ONE PASS THAT REUSES ITS WORK · 02
SOLVED HAS A JUDGE LINK
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
03 / MECHANISM UNIT 01 · THE PREFIX FUNCTION

FALL BACK ALONG THE BORDERS

pi[i] is the longest border of s[0..i]. Try to extend the border before it by one letter. When the letter misses, the next border to try is the longest border of that border, pi[k − 1]. k rises at most once per letter, so all the falls together cost O(n).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
04 / DRILL UNIT 01 · The Prefix Function · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

longestPrefix("ababab")?

ababab has the borders ab and abab, and a border is shorter than the string, so abab is the longest. pi runs 0, 0, 1, 2, 3, 4.

DRILL 02 · RECALL

On a miss, why is the next k equal to pi[k − 1]?

Every border of s[0..i − 1] shorter than k ends where the length-k border ends, so it is a border of that border too. The longest of those is pi[k − 1].

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
05 / PROBLEM #01 · PI · HARD

Longest Happy Prefix

HARD pi ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Return the longest happy prefix: a non-empty prefix that is also a suffix, not the whole string.

INTUITION

A prefix that is also a suffix is a border. Let pi[i] be the length of the longest border of s[0..i]. A border of s[0..i] is a border of s[0..i − 1] extended by s[i], so try the longest one, k = pi[i − 1]: if s[k] equals s[i], pi[i] = k + 1. If not, the next border to try is the longest border of that border, pi[k − 1], and so on down to 0. Each step down shortens k, and k grows by at most 1 per letter, so the whole pass is O(n). The answer is the prefix of length pi[n − 1].

STEPS
  1. pi[0] = 0
  2. For each i, start from k = pi[i − 1]
  3. While s[i] differs from s[k] and k > 0, fall back to k = pi[k − 1]
  4. If they match, k grows by 1; pi[i] = k
  5. Return the first pi[n − 1] letters
BRUTEO(n²), comparing every prefix with its suffix
→
OPTIMALO(n)
↕ SCROLL
string longestPrefix(string s) {
    int n = s.size();
    vector<int> pi(n, 0);                      // pi[i]: longest border of s[0..i]
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];                     // the border to try to extend
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return s.substr(0, pi[n - 1]);
}
TIMEO(n)k rises at most n times in all, so it falls at most n times
SPACEO(n)the pi array
TRAP

Falling back to k − 1. A shorter length need not be a border, so the next one to try is pi[k − 1]. In abcabb the last b fails against c with k = 2. Trying k − 1 = 1 compares it with s[1] = b, a match, and the answer comes out ab, though abcabb ends in bb.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
06 / PROBLEM #02 · PI · EASY

Finding Borders

EASY pi ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Print the lengths of every border of a string of up to 10⁶ letters, in increasing order.

INTUITION

The longest border has length pi[n − 1]. Every shorter border of the string is also a border of that border, so the next one is pi[pi[n − 1] − 1], and so on until 0. Walking that chain lists every border, longest first, in O(n) after the prefix function is built; print it reversed.

STEPS
  1. Build pi for the whole string
  2. Start at k = pi[n − 1] and step k = pi[k − 1] while k > 0
  3. Print the lengths met, reversed so they increase
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

vector<int> prefixFunction(const string& s) {   // pi[i]: longest border of s[0..i]
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

int main() {
    string s;
    cin >> s;
    vector<int> pi = prefixFunction(s);
    vector<int> out;
    for (int k = pi.back(); k > 0; k = pi[k - 1]) out.push_back(k);   // longest first
    reverse(out.begin(), out.end());
    string line;
    for (size_t t = 0; t < out.size(); t++) line += (t ? " " : "") + to_string(out[t]);
    puts(line.c_str());
}
TIMEO(n)one prefix function and a chain of at most n steps
SPACEO(n)the pi array
TRAP

Stopping after the longest border. In abcababcab the longest border is abcab, and ab is a border of it. Printing only pi[n − 1] gives 5; the chain gives 2 5.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
07 / DRILL UNIT 01 · The Prefix Function · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Finding Borders on abacaba?

pi ends in 3, the border aba. Its own longest border is a, of length 1, and a has none. Printed in increasing order, 1 3.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
08 / MECHANISM UNIT 02 · MATCH WITHOUT STEPPING BACK

SLIDE THE NEEDLE, NEVER THE TEXT

k counts the needle letters matched. On a miss the needle slides so that its longest border lines up with the end of what matched, k = pi[k − 1], and the same text letter is tried again. i never moves back.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
09 / DRILL UNIT 02 · Match Without Stepping Back · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

strStr("mississippi", "issip")?

issi matches at 1, and then p misses s. issi ends in i, which is how issip starts, so the needle slides to 4 and fits there.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
10 / PROBLEM #03 · KMP · EASY

Find the Index of the First Occurrence in a String

EASY kmp ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Return the index of the first occurrence of needle in haystack, or −1.

INTUITION

Comparing needle at every start redoes work after each mismatch. KMP keeps k, the number of needle letters matched so far, and never moves back in haystack. On a mismatch the matched part is needle[0..k − 1], and the longest of its borders is the most that can still be matched, so k becomes pi[k − 1] and the same haystack letter is tried again. When k reaches m the match ends at i, so it starts at i − m + 1.

STEPS
  1. Build pi for needle
  2. Walk haystack once, with k needle letters matched
  3. On a mismatch, fall back to k = pi[k − 1] until the letter fits or k = 0
  4. On a match, k grows by 1; at k = m return i − m + 1
BRUTEO(n · m)
→
OPTIMALO(n + m)
↕ SCROLL
vector<int> prefixFunction(const string& s) {   // pi[i]: longest border of s[0..i]
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

int strStr(string haystack, string needle) {
    int m = needle.size();
    vector<int> pi = prefixFunction(needle);
    int k = 0;                                 // needle letters matched so far
    for (int i = 0; i < (int)haystack.size(); i++) {
        while (k > 0 && haystack[i] != needle[k]) k = pi[k - 1];   // the longest border that fits
        if (haystack[i] == needle[k]) k++;
        if (k == m) return i - m + 1;
    }
    return -1;
}
TIMEO(n + m)i only moves forward, and k falls no more than it rises
SPACEO(m)pi for needle
TRAP

Dropping to k = 0 on a mismatch. The letters matched so far may end in a shorter start of needle. In haystack aaab with needle aab, the third a breaks aa + b. Dropping to 0 keeps only that a, the b then fails, and the search returns −1 instead of 1. Falling back to pi[1] = 1 keeps aa.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
11 / PROBLEM #04 · KMP · EASY

String Matching

EASY kmp ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Count the positions where a pattern occurs in a string, both up to 10⁶ letters.

INTUITION

The same scan as unit 2's search, with one change after a full match. Instead of stopping, count it and fall back to k = pi[m − 1], the longest border of the whole pattern. That keeps overlapping occurrences: in aaaa the pattern aa occurs 3 times.

STEPS
  1. Build pi for the pattern
  2. Scan the string with k letters matched, falling back on mismatches
  3. At k = m, count one occurrence and set k = pi[m − 1]
BRUTEO(n · m)
→
OPTIMALO(n + m)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

vector<int> prefixFunction(const string& s) {   // pi[i]: longest border of s[0..i]
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

int main() {
    string s, p;
    cin >> s >> p;
    vector<int> pi = prefixFunction(p);
    int k = 0, m = p.size();
    long long cnt = 0;
    for (char ch : s) {
        while (k > 0 && ch != p[k]) k = pi[k - 1];
        if (ch == p[k]) k++;
        if (k == m) { cnt++; k = pi[m - 1]; }  // keep overlapping matches
    }
    printf("%lld\n", cnt);
}
TIMEO(n + m)one pass over each string
SPACEO(m)pi for the pattern
TRAP

Starting over after a match. Setting k = 0 after each match skips occurrences that overlap it. In aaaa, the pattern aa is counted at 0 and 2 but not at 1, so the count is 2 instead of 3.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
12 / DRILL UNIT 02 · Match Without Stepping Back · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

String Matching with the string abababa and the pattern aba?

aba occurs at 0, 2 and 4, each overlapping the next. After each match k falls to pi[2] = 1 and keeps the final a.

DRILL 02 · RECALL

After a full match, why is k set to pi[m − 1] rather than 0?

In aaaa the matches of aa at 0, 1 and 2 overlap. Keeping the border a lets the match at 1 grow from it.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
13 / MECHANISM UNIT 03 · A BORDER GIVES THE PERIOD

THE COPIES REPEAT, SO THE SCAN ENDS

A border of length b means a string repeats every n − b letters. The endless copies of a repeat every n letters, so a match starting at n or later repeats one that starts n earlier. KMP over n + m letters finds the first match or proves there is none.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
14 / DRILL UNIT 03 · A Border Gives the Period · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

repeatedSubstringPattern("abcabcab")?

The longest border is abcab, so the shortest period is 8 − 5 = 3. Eight letters do not split into copies of abc.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
15 / PROBLEM #05 · PI · EASY

Repeated Substring Pattern

EASY pi ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Can the string be built by repeating one of its substrings several times?

INTUITION

If s has a border of length b, then s matches itself shifted by p = n − b, so s repeats with period p, the last copy perhaps cut short. The longest border gives the shortest period. s is a whole number of copies of its first p letters exactly when p divides n, and p < n, so a border exists.

STEPS
  1. Build pi for s
  2. The shortest period is p = n − pi[n − 1]
  3. Return true when pi[n − 1] > 0 and n % p == 0
↕ SCROLL
vector<int> prefixFunction(const string& s) {   // pi[i]: longest border of s[0..i]
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

bool repeatedSubstringPattern(string s) {
    int n = s.size(), b = prefixFunction(s).back();   // the longest border
    return b > 0 && n % (n - b) == 0;          // n - b: the shortest period
}
TIMEO(n)one prefix function
SPACEO(n)the pi array
TRAP

A border is not enough. abcab has the border ab, so it has period 3, but its 5 letters do not split into copies of abc. Without the test that 3 divides 5 it returns true.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
16 / PROBLEM #06 · KMP · MED

Repeated String Match

MED kmp ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Repeat a the fewest times so that b becomes a substring of the result, or return −1.

INTUITION

Search b in the endless text a a a … with KMP, reading the text letter a[i % n]. A match that starts at or after n repeats one that starts n earlier and needs one more copy, so a first match, if any, starts before n and ends before n + m. The scan therefore stops at i = n + m. The first match found ends earliest, and ending at index i it reaches into copy i / n + 1.

STEPS
  1. Build pi for b
  2. Scan i from 0 to n + m − 1, reading a[i % n], with k letters of b matched
  3. At k = m return i / n + 1
  4. If the scan ends, return −1
BRUTEO((n + m) · m), building copies and searching
→
OPTIMALO(n + m)
↕ SCROLL
vector<int> prefixFunction(const string& s) {   // pi[i]: longest border of s[0..i]
    vector<int> pi(s.size(), 0);
    for (int i = 1; i < (int)s.size(); i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) k = pi[k - 1];   // fall back to a shorter border
        if (s[i] == s[k]) k++;
        pi[i] = k;
    }
    return pi;
}

int repeatedStringMatch(string a, string b) {
    int n = a.size(), m = b.size();
    vector<int> pi = prefixFunction(b);
    int k = 0;
    for (int i = 0; i < n + m; i++) {          // a start past the first copy repeats one
        char ch = a[i % n];                    // the text is a, a, a, ...
        while (k > 0 && ch != b[k]) k = pi[k - 1];
        if (ch == b[k]) k++;
        if (k == m) return i / n + 1;          // the copies the match reaches into
    }
    return -1;
}
TIMEO(n + m)at most n + m text letters
SPACEO(m)pi for b
TRAP

Stopping at m letters of text. A bound of max(n, m) letters looks safe but misses matches that start late in the first copy. With a = "abc" and b = "cab", the match starts at 2 and ends at 4; a scan of 3 letters returns −1 instead of 2.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
17 / DRILL UNIT 03 · A Border Gives the Period · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

repeatedStringMatch("abc", "cabcab")?

In abcabcabc, cabcab starts at 2 and ends at 7, inside the third copy. 7 / 3 + 1 = 3.

DRILL 02 · RECALL

Why can the scan stop after n + m letters of a, a, a, …?

The text repeats every n letters, so a match starting at s ≥ n copies one starting at s − n. A first match starts below n and so ends before n + m.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
18 / MECHANISM UNIT 04 · JOIN WITH A SEPARATOR

A PALINDROME IS A BORDER OF THE JOIN

A prefix of s is a palindrome exactly when reverse(s) ends with it. So the longest one is the longest border of s + # + reverse(s), and the # keeps that border inside s. The letters after it are mirrored and put in front.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
19 / DRILL UNIT 04 · Join With a Separator

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

shortestPalindrome("abb")?

The longest palindrome starting abb is a. The rest, bb, goes in front reversed, and bb + abb = bbabb.

DRILL 02 · RECALL

Why put a # between s and its reverse?

Without it, s = aa gives t = aaaa, whose border aaa is longer than s. The # matches no letter, so every border of t ends inside s.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
20 / PROBLEM #07 · PI · HARD

Shortest Palindrome

HARD pi ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Add letters in front of s to make the shortest palindrome.

INTUITION

Whatever goes in front must mirror what is left after the longest palindrome that starts s. So the task is that palindrome's length. A prefix of s is a palindrome exactly when it equals a suffix of reverse(s), so it is the longest border of s + "#" + reverse(s). The # can match nothing, so no border runs across it. If the border has length keep, reverse the rest of s and put it in front.

STEPS
  1. Build t = s + "#" + reverse(s)
  2. keep = pi[last] of t, the longest palindrome starting s
  3. Return reverse(s[keep..]) + s
BRUTEO(n²), testing each prefix for a palindrome
→
OPTIMALO(n)
↕ SCROLL
string shortestPalindrome(string s) {
    string r(s.rbegin(), s.rend());
    string t = s + "#" + r;                    // # keeps a border inside s
    int n = t.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];
        while (k > 0 && t[i] != t[k]) k = pi[k - 1];
        if (t[i] == t[k]) k++;
        pi[i] = k;
    }
    int keep = pi[n - 1];                      // the longest palindrome starting s
    return r.substr(0, s.size() - keep) + s;
}
TIMEO(n)one prefix function over 2n + 1 letters
SPACEO(n)t and its pi array
TRAP

Joining without the #. For s = "aa", t = "aaaa" has a border of 3, longer than s, and r.substr(0, 2 − 3) fails. The separator caps every border at n, so keep never passes the length of s.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
21 / MECHANISM UNIT 05 · THE Z FUNCTION

COPY FROM THE BOX, THEN COMPARE PAST IT

z[i] is how far s[i..] matches the start. The box [l, r) is the match reaching furthest right. For i inside it, s[i..r) is a copy of s[i − l..r − l), so z[i] starts at min(r − i, z[i − l]) and only letters past r are compared.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
22 / DRILL UNIT 05 · The Z Function · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

In the Z function of aabxaab, what is z[4]?

s[4..] is aab, which is how s starts, so 3 letters match before the string ends.

DRILL 02 · RECALL

Why does z[i] start at min(r − i, z[i − l]) and not at z[i − l]?

Inside the box, s[i..r) is a copy of s[i − l..r − l). What z[i − l] says about letters past r − l tells nothing about the letters past r.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
23 / PROBLEM #08 · Z · MED

Finding Periods

MED z ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Print every period of a string of up to 10⁶ letters: a prefix that, repeated, generates the whole string, the last copy perhaps cut short.

INTUITION

Let z[i] be the length of the longest common prefix of s and s[i..]. A shift p is a period when s[p..] matches the start of s all the way to the end, which is p + z[p] = n, and n itself is always one. The Z function keeps a box [l, r): the match that reaches furthest right. For i inside the box, s[i..r) is a copy of s[i − l .. r − l), so z[i] starts from min(r − i, z[i − l]) and only grows by comparing past r. r only moves right, so the pass is O(n).

STEPS
  1. z[0] is left as 0, with the box [l, r) empty
  2. For i inside the box, start z[i] at min(r − i, z[i − l])
  3. Extend z[i] by comparing s[z[i]] with s[i + z[i]]
  4. If i + z[i] passes r, the box becomes [i, i + z[i])
  5. Print every p with p + z[p] = n, then n
BRUTEO(n²), testing every period
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> z(n, 0);                       // z[i]: how far s[i..] matches s
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);   // copy from inside the box
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }   // a box reaching further
    }
    string out;
    for (int p = 1; p < n; p++)
        if (p + z[p] == n) out += to_string(p) + " ";   // shift p matches to the end
    out += to_string(n);
    puts(out.c_str());
}
TIMEO(n)every comparison that succeeds moves r right
SPACEO(n)the z array
TRAP

Copying z[i − l] past the box. Only s[i..r) is known to copy s[i − l..r − l). In aaa the box at i = 2 is [1, 3) and z[1] = 2. Copied whole, z[2] = 2 runs past the end, the test 2 + z[2] = 3 fails, and the period 2 is lost. The min with r − i gives z[2] = 1.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
24 / PROBLEM #09 · Z · MED

Password

MED z ▶ SOLVE ON CODEFORCESCodeforces 126B, rated 1700.
SIGNAL — WHAT GIVES IT AWAY

Find the longest substring that is a prefix, a suffix, and also occurs inside the string, neither at its start nor at its end.

INTUITION

With the Z function, the suffix starting at i equals the prefix of the same length exactly when i + z[i] = n, so its length is n − i. It also occurs inside if some earlier start j, 1 ≤ j < i, matches at least that much of the prefix: z[j] ≥ n − i. A later start cannot fit that many letters. Scanning i upwards tries the longest candidates first while keeping the largest z[j] seen so far, so the first i that passes gives the answer.

STEPS
  1. Build z for s
  2. Scan i from 1, keeping the largest z[j] over 1 ≤ j < i
  3. If i + z[i] = n and that largest z[j] ≥ n − i, print the first n − i letters
  4. If no i passes, print "Just a legend"
BRUTEO(n²)
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    int inside = 0;                            // the largest z[j] for 1 <= j < i
    for (int i = 1; i < n; i++) {
        if (i + z[i] == n && inside >= n - i) {   // a suffix that is a prefix, seen inside
            puts(s.substr(0, n - i).c_str());
            return 0;
        }
        inside = max(inside, z[i]);
    }
    puts("Just a legend");
}
TIMEO(n)one Z function and one scan
SPACEO(n)the z array
TRAP

Counting the suffix itself as inside. Taking the largest z over all j, i included, lets the suffix vouch for itself. On abcdabc it prints abc, but abc occurs only as the prefix and the suffix, so the answer is "Just a legend".

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
25 / DRILL UNIT 05 · The Z Function · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Password on abcabcabc?

abcabc is a prefix and a suffix, but it occurs only at 0 and at 3, where the suffix starts. abc is a prefix and a suffix and also starts at 3, in the middle.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
26 / MECHANISM UNIT 06 · A CODE FOR EVERY WINDOW

SHIFT IN, MASK OUT

A window of k bits is a k-bit number. Sliding by one bit is a shift, an OR with the new bit, and a mask that drops the bit that left. The code is exact, so one flag per code counts the different windows.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
27 / DRILL UNIT 06 · A Code for Every Window · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

In Repeated DNA Sequences, why does a 20-bit code stand for a window with no collisions?

A, C, G and T are 0 to 3, two bits each, so 10 letters fill 20 bits and different windows are different numbers.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
28 / PROBLEM #10 · HASH · MED

Repeated DNA Sequences

MED hash ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Return every 10-letter sequence of a DNA string that occurs more than once.

INTUITION

With four letters, each fits in 2 bits, so a 10-letter window is a 20-bit number with no collisions. Sliding one letter is a shift left by 2, an OR with the new letter, and a mask that drops the letter that left. Count each window's code in a map, and report a window the moment its count reaches 2, so it is reported once.

STEPS
  1. Code A, C, G, T as 0 to 3
  2. Slide h = ((h << 2) | code) & (2²⁰ − 1) over the string
  3. From the tenth letter on, count h; at a count of 2, report that window
BRUTEO(10n) with a hash set of substrings
→
OPTIMALO(n)
↕ SCROLL
vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<char, int> code = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
    unordered_map<int, int> seen;              // window code -> times seen
    vector<string> out;
    int h = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        h = ((h << 2) | code[s[i]]) & ((1 << 20) - 1);   // the last 10 letters, 2 bits each
        if (i >= 9 && ++seen[h] == 2) out.push_back(s.substr(i - 9, 10));
    }
    return out;
}
TIMEO(n)one step per letter
SPACEO(n)the counts of the windows
TRAP

Reporting at every repeat. Adding the window whenever its count is above 1 lists a sequence once per extra occurrence. In "AAAAAAAAAAAAA", AAAAAAAAAA occurs 4 times and would be returned 3 times.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
29 / PROBLEM #11 · HASH · MED

Check If a String Contains All Binary Codes of Size K

MED hash ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A binary string and k. Is every k-bit code a substring?

INTUITION

There are 2ᵏ codes, and each window of k bits is one of them, read as a number. Slide that number along the string with a shift, an OR and a mask, mark each code seen, and count the new ones. When the count reaches 2ᵏ, every code has appeared. Each step is O(1), and nothing is ever hashed, so there are no collisions.

STEPS
  1. need = 2ᵏ codes still missing
  2. Slide h = ((h << 1) | bit) & (2ᵏ − 1)
  3. From the k-th bit on, a code not yet seen is marked and need drops by 1
  4. Return true when need reaches 0, false at the end
BRUTEO(n · k) with a set of substrings
→
OPTIMALO(n)
↕ SCROLL
bool hasAllCodes(string s, int k) {
    int need = 1 << k, mask = need - 1, h = 0;
    vector<bool> seen(need, false);
    for (int i = 0; i < (int)s.size(); i++) {
        h = ((h << 1) | (s[i] - '0')) & mask;  // the last k bits
        if (i < k - 1 || seen[h]) continue;
        seen[h] = true;                        // a new code
        if (--need == 0) return true;
    }
    return false;
}
TIMEO(n)one step per bit
SPACEO(2ᵏ)one flag per code
TRAP

Counting before the window is full. Marking h from the very first bit counts codes of fewer than k bits. With s = "0110" and k = 2, the first bit alone marks code 0, which is 00, and the answer comes out true when 00 never occurs.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
30 / DRILL UNIT 06 · A Code for Every Window · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

hasAllCodes("0110", 2)?

The windows are 01, 11 and 10. 00 never occurs.

DRILL 02 · RECALL

What does & mask do in h = ((h << 1) | bit) & mask?

After the shift, h holds k + 1 bits. The mask keeps the low k, which are the window's.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
31 / MECHANISM UNIT 07 · BINARY SEARCH ON THE LENGTH

SEARCH THE LENGTH, HASH THE WINDOWS

A repeat of length L contains one of length L − 1, so the length can be binary searched. Each test slides a hash over the windows of one length. Equal hashes are only a hint, so the letters are compared. The bench hashes mod 67 so a collision shows.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
32 / DRILL UNIT 07 · Binary Search on the Length · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

longestDupSubstring("aaaaa")?

aaaa occurs at 0 and at 1. The two copies overlap, which is allowed, so the answer can be n − 1 letters long.

DRILL 02 · RECALL

Why can the answer's length be binary searched?

Both copies of a repeated L-letter piece start with the same L − 1 letters. So the lengths that repeat run from 1 up to the best, and the test is yes up to it and no after.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
33 / PROBLEM #12 · HASH · HARD

Longest Duplicate Substring

HARD hash ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Return a longest substring that occurs twice (the copies may overlap), or "".

INTUITION

If some substring of length L occurs twice, so does one of length L − 1, its prefix. So the answer's length can be binary searched, and each test asks whether any L-letter window repeats. Hash every window with a rolling polynomial hash mod 10⁹ + 7, sliding in O(1). Equal hashes might come from different windows, so on a hit the letters are compared before the repeat is accepted. Each test is O(n) expected, and there are O(log n) of them.

STEPS
  1. Binary search L over 1 to n − 1
  2. For a length L, hash the first window, then slide: drop the old letter, add the new one
  3. On equal hashes, compare the windows' letters; a true repeat passes the test
  4. Keep the longest L that passes and where its repeat starts
BRUTEO(n³)
→
OPTIMALO(n log n) expected
↕ SCROLL
const long long P = 1000000007, B = 131;

int dup(const string& s, int L) {             // the start of a repeated window, or -1
    long long h = 0, pw = 1;
    for (int i = 0; i < L; i++) {
        h = (h * B + s[i]) % P;
        pw = pw * B % P;                       // B^L, the weight of the letter leaving
    }
    unordered_map<long long, vector<int>> seen{{h, {0}}};
    for (int i = L; i < (int)s.size(); i++) {
        h = ((h * B - s[i - L] * pw % P + P) + s[i]) % P;   // slide one letter
        int st = i - L + 1;
        for (int j : seen[h])                  // equal hashes: check the letters
            if (s.compare(j, L, s, st, L) == 0) return st;
        seen[h].push_back(st);
    }
    return -1;
}

string longestDupSubstring(string s) {
    int lo = 1, hi = s.size() - 1, best = 0, at = 0;
    while (lo <= hi) {                         // a repeat of L letters means one of L - 1
        int mid = (lo + hi) / 2, st = dup(s, mid);
        if (st >= 0) { best = mid; at = st; lo = mid + 1; }
        else hi = mid - 1;
    }
    return s.substr(at, best);
}
TIMEO(n log n) expectedO(n) per length tested, O(log n) lengths
SPACEO(n)the windows by hash
TRAP

Trusting equal hashes. Two different windows can share a hash mod 10⁹ + 7. Accepting a hit without comparing the letters returns a substring that occurs once. Comparing on every hit costs little, since true collisions are rare.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
34 / PROBLEM #13 · HASH · MED

Maximum Length of Repeated Subarray

MED hash ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Two integer arrays. Return the length of the longest subarray that appears in both.

INTUITION

As in Longest Duplicate Substring, a common subarray of length L has a common prefix of length L − 1, so binary search the length. For a length L, hash every window of nums1 into a map from hash to start positions, then slide over nums2 and look each hash up. The values run from 0 to 100, so the base must be above 100. On a hit, compare the two windows value by value.

STEPS
  1. Binary search L over 1 to min(n, m)
  2. Hash every L-window of nums1, keeping its starts by hash
  3. Slide over nums2; on a hash found, compare the windows
  4. Keep the longest L with a true match
BRUTEO(n · m) dp, or O(n · m · min) by brute force
→
OPTIMALO((n + m) log min(n, m)) expected
↕ SCROLL
int findLength(vector<int>& nums1, vector<int>& nums2) {
    const long long P = 1000000007, B = 113;   // values are 0..100, so B > 100
    int n = nums1.size(), m = nums2.size();
    auto common = [&](int L) {                 // is some L-long window in both?
        long long pw = 1, h = 0;
        for (int i = 0; i < L; i++) pw = pw * B % P;
        unordered_map<long long, vector<int>> seen;   // hash -> starts in nums1
        for (int i = 0; i < n; i++) {
            h = (h * B + nums1[i]) % P;
            if (i >= L) h = (h - nums1[i - L] * pw % P + P) % P;
            if (i >= L - 1) seen[h].push_back(i - L + 1);
        }
        h = 0;
        for (int i = 0; i < m; i++) {
            h = (h * B + nums2[i]) % P;
            if (i >= L) h = (h - nums2[i - L] * pw % P + P) % P;
            if (i < L - 1 || !seen.count(h)) continue;
            for (int j : seen[h])              // equal hashes: check the values
                if (equal(nums1.begin() + j, nums1.begin() + j + L, nums2.begin() + i - L + 1))
                    return true;
        }
        return false;
    };
    int lo = 1, hi = min(n, m), best = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (common(mid)) { best = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return best;
}
TIMEO((n + m) log min(n, m)) expectedO(n + m) per length, O(log) lengths
SPACEO(n)nums1's windows by hash
TRAP

Carrying the hash into the second array. After the pass over nums1, h still holds its last window. Without h = 0, the windows of nums2 hash as if they went on from nums1, and matches are missed. On [1, 2] and [1, 2] it returns 0 instead of 2.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
35 / DRILL UNIT 07 · Binary Search on the Length · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

findLength([1, 2, 3, 2, 1], [3, 2, 1, 4, 7])?

[3, 2, 1] is in both, at 2 in the first and at 0 in the second. No 4 values in a row are shared.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
36 / MECHANISM UNIT 08 · MIRROR INSIDE THE RIGHTMOST PALINDROME

MIRROR INSIDE THE RIGHTMOST PALINDROME

With a # between letters every palindrome has one centre. Keep the palindrome that reaches furthest right, centred at c and ending at r. A centre inside it starts from its mirror's radius, cut at r, and only letters past r are compared.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
37 / DRILL UNIT 08 · Mirror Inside the Rightmost Palindrome · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Longest Palindrome on zabacabz?

zabacabz reads zbacabaz backwards, so it is not one. Around the c, bacab reads the same both ways, and the next pair, a and z, differs.

DRILL 02 · RECALL

Why put a # between the letters?

abba has its centre between the two b. In #a#b#b#a# that centre is a #, so one loop over centres finds palindromes of both lengths.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
38 / DRILL UNIT 08 · Mirror Inside the Rightmost Palindrome · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why does the pass stay O(n)?

A centre inside the box starts from its mirror's radius cut at r, so matching comparisons happen only past r. r stays below 2n + 1, and each centre adds one failed comparison at most.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
39 / PROBLEM #14 · REUSE · MED

Longest Palindrome

MED reuse ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Print a longest palindromic substring of a string of up to 10⁶ letters.

INTUITION

Expanding around every centre is O(n²) on aaaa…a. Manacher's algorithm puts a # between letters so every palindrome has a single centre, then keeps the palindrome that reaches furthest right, centred at c and ending at r. A centre i inside it has a mirror 2c − i, and the palindrome around the mirror is copied around i, up to the edge r. Only letters past r are compared, and r only moves right, so the pass is O(n).

STEPS
  1. Build t = # s₀ # s₁ # … # (2n + 1 letters)
  2. For each i, start p[i] at min(r − i, p[2c − i]) if i < r, else 0
  3. Extend p[i] while the letters on both sides match
  4. If i + p[i] passes r, take c = i, r = i + p[i]
  5. The largest p[i] is the length, starting at (i − p[i]) / 2 in s
BRUTEO(n²), expanding around every centre
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    string t = "#";                            // a # between letters: one centre each
    for (char ch : s) { t += ch; t += '#'; }
    int n = t.size(), c = 0, r = 0, best = 0, at = 0;
    vector<int> p(n, 0);                       // p[i]: the palindrome's length in s
    for (int i = 0; i < n; i++) {
        if (i < r) p[i] = min(r - i, p[2 * c - i]);   // the mirror inside the box
        while (i - p[i] > 0 && i + p[i] + 1 < n
               && t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }    // a palindrome reaching further
        if (p[i] > best) { best = p[i]; at = (i - p[i]) / 2; }
    }
    puts(s.substr(at, best).c_str());
}
TIMEO(n)every successful comparison moves r right
SPACEO(n)t and the radii
TRAP

Copying the mirror past the edge. Only the part of the mirror's palindrome inside the box is known to repeat. Taking p[2c − i] without the min with r − i claims letters past r, and the extension starts from a wrong radius. On ababbb it prints babbb, which is not a palindrome.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
40 / MECHANISM UNIT 09 · TWO CANDIDATES, SKIP THE LOSER

THE LOSER JUMPS PAST ALL IT COVERS

Compare the rotations at i and j letter by letter. When they differ after k equal letters, the loser and the k starts after it all lose to the starts the same distance after the winner. So the loser jumps by k + 1, and every step moves i, j or k forward.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
41 / DRILL UNIT 09 · Two Candidates, Skip the Loser · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Minimal Rotation of cbab?

The rotations are cbab, babc, abcb and bcba. abcb is the only one starting with a.

DRILL 02 · RECALL

When i loses after k equal letters, why may i jump to i + k + 1?

The rotation at i + t agrees with the one at j + t for k − t letters, then has the same larger letter. So every start from i to i + k is beaten, and none can be the answer.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
42 / DRILL UNIT 09 · Two Candidates, Skip the Loser · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Without if (i == j) j++, what does Minimal Rotation print for cba?

i = 0 loses to j = 1 and jumps to 1. With i = j each comparison is a letter against itself, so k runs to 3 and the loop ends with min(i, j) = 1. bac is printed, and the answer is acb.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
43 / PROBLEM #15 · REUSE · HARD

Minimal Rotation

HARD reuse ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. Submit the Python tab as PyPy3.
SIGNAL — WHAT GIVES IT AWAY

Print the lexicographically smallest rotation of a string of up to 10⁶ letters.

INTUITION

Keep two candidate starts, i and j, and compare their rotations letter by letter, with k letters equal so far. When s[i + k] > s[j + k], the rotation at i loses, and so does every rotation starting in i + 1 .. i + k: each is beaten by the one starting the same distance after j. So i jumps to i + k + 1, and the same holds the other way round. The two starts only move forward, so the scan is O(n), and when one passes n the other is the answer.

STEPS
  1. Start with i = 0, j = 1, k = 0
  2. Compare s[(i + k) % n] with s[(j + k) % n]; on equal letters k grows
  3. On a difference, the loser's start jumps by k + 1, j moves on if the two meet, and k = 0
  4. Stop when a start reaches n or k reaches n; the answer starts at min(i, j)
BRUTEO(n²), comparing every rotation
→
OPTIMALO(n)
↕ SCROLL
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size(), i = 0, j = 1, k = 0;     // two candidate starts
    while (i < n && j < n && k < n) {
        char a = s[(i + k) % n], b = s[(j + k) % n];
        if (a == b) { k++; continue; }
        if (a > b) i += k + 1;                 // i .. i + k all lose to j .. j + k
        else j += k + 1;
        if (i == j) j++;
        k = 0;
    }
    int st = min(i, j);
    puts((s.substr(st) + s.substr(0, st)).c_str());
}
TIMEO(n)i + j + k grows with every comparison and stays under 3n
SPACEO(1)beyond the string
TRAP

Letting the two starts meet. A jump can land the loser on the other start. In cba, i = 0 loses to j = 1 and jumps to 1. The two then compare one rotation with itself, k runs to n, and bac is printed instead of acb. Moving j on when they meet keeps two candidates.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
44 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Nine moves, and each has a phrase in the statement that gives it away.

THE LONGEST PREFIX THAT IS ALSO A SUFFIX

the prefix function, falling back along pi[k − 1]

PREFIX FUNCTIONO(n)
FIND OR COUNT A PATTERN IN A TEXT

match with k, and slide the pattern by its border

KMP SEARCHO(n + m)
IS IT ONE PIECE REPEATED, OR HOW MANY REPEATS HOLD IT

the shortest period is n − pi[n − 1]

BORDER AND PERIODO(n)
A PALINDROME AT THE START OF A STRING

the longest border of s + # + reverse(s)

JOIN WITH #O(n)
HOW FAR EACH SUFFIX MATCHES THE START

the Z function, copying from the box

Z FUNCTIONO(n)
EVERY WINDOW OF FIXED LENGTH, COUNTED OR CHECKED

an exact code with a shift, an OR and a mask

ROLLING CODEO(n)
THE LONGEST REPEATED OR SHARED PIECE

binary search the length and hash the windows

SEARCH AND HASHO(n log n)
THE LONGEST PALINDROME IN 10⁶ LETTERS

mirror inside the rightmost palindrome

MANACHERO(n)
THE SMALLEST ROTATION

two candidates, and the loser jumps by k + 1

MINIMUM ROTATIONO(n)
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
45 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Count how often a word occurs in a book, overlapping occurrences included. Which move?

KMP over the book, falling back to pi[m − 1] after each match so overlaps count. It is String Matching with a longer text.

DRILL 02 · TRANSFER

Rotate String asks whether goal is a rotation of s. Which move answers it in O(n)?

goal is a rotation of s when the two have one length and goal occurs in s + s. A KMP search for it reads 2n letters once. The strings deck checks the same thing more slowly.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
46 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

Longest Palindromic Substring, in linear time. Which move?

Manacher's pass, as in CSES Longest Palindrome. Joining s with its reverse finds only palindromes at the start. For n up to 1000, expanding around every centre is fast enough.

DRILL 02 · RECALL

Why must a rolling hash compare letters on equal hashes, when a rolling code need not?

A code keeps every letter in bits of its own, so one code means one window. A hash folds the window mod P, and different windows can land on one value, as bana and anan did mod 67.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
47 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

FALLING BACK BY ONE

On a miss the next border to try is pi[k − 1], not k − 1. A shorter length need not be a border at all.

STARTING OVER AFTER A MATCH

Counting with k = 0 after each match loses the occurrences that overlap it. Fall back to pi[m − 1] instead.

A BORDER THAT CROSSES THE JOIN

Joining s and reverse(s) with nothing between them lets a border run past s. A letter in neither string stops it.

COPYING PAST THE BOX

The Z function and Manacher may copy only what lies before r. Take the min with r − i before comparing.

TRUSTING EQUAL HASHES

Two windows can share a hash mod P. Compare the letters before a repeat counts.

COUNTING A WINDOW BEFORE IT IS FULL

A rolling code stands for a whole window only from the k-th letter on. Skip the first k − 1.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
48 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Nine moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Prefix function
O(n)
O(n)
k = pi[i − 1]; on a miss k = pi[k − 1]; on a match k++
KMP search
O(n + m)
O(m)
the same loop over the text; at k = m, k = pi[m − 1]
Border and period
O(n)
O(n)
period n − pi[n − 1]; whole copies if it divides n
Join with #
O(n)
O(n)
pi of s # reverse(s) ends in the palindrome's length
Z function
O(n)
O(n)
z[i] = min(r − i, z[i − l]), then extend past r
Rolling code
O(n)
O(2ᵏ)
h = ((h << b) | c) & mask, from the k-th letter
Search and hash
O(n log n)
O(n)
binary search L; slide a hash; compare when equal
Manacher
O(n)
O(n)
# between letters; p[i] = min(r − i, p[2c − i])
Minimum rotation
O(n)
O(1)
the loser jumps k + 1; if i = j then j++
INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
49 / CLOSE MODULE 29 · ADVANCED STRINGS

TAKE IT NOW

The prefix function fell back along the borders; KMP slid the needle and never the text; a border gave the period, and the copies of a gave the scan its end; s # reverse(s) found the palindrome at the start; the Z function copied from its box; an exact code slid over every window; a binary search on the length hashed the windows and compared on equal hashes; Manacher mirrored inside the rightmost palindrome; and the smaller rotation won while the loser jumped. Longest Palindromic Substring and Rotate String are in the strings deck.

00%
OF THIS DECK SOLVED
← ALL TOPICS← STRINGS← HASHING

Module 29. Fifteen problems: nine on LeetCode, five on CSES and one on Codeforces. Next in the sheet: range queries, an optional lane.

INVARIANT · STRINGS · NEVER COMPARE THE SAME LETTER TWICE · ADVANCED STRINGS
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 29 · ADVANCED STRINGS

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.