Why naive matching is quadratic
Checking a pattern of length m at every start in a text of length n costs O(n · m) in the worst case, for example searching aaaab inside a long run of a characters. Each failed attempt throws away the knowledge that the previous characters matched. Linear-time matchers keep that knowledge: KMP stores, for every pattern prefix, the length of its longest proper prefix that is also a suffix, so after a mismatch it resumes from that border instead of restarting.
Rolling hashes and their limits
Rabin–Karp computes a polynomial hash of each window in O(1) by removing the outgoing character and adding the incoming one. Equal hashes only suggest a match; collisions mean candidates must be verified, or a double hash with two moduli used to make collisions unlikely. Expected time is O(n + m), but adversarial inputs against a fixed modulus can force many collisions. Rolling hashes also compare substrings in O(1) for problems such as longest duplicate substring with binary search.
Bit manipulation as a data structure
An int can represent a subset of up to 32 items: x & (1 << i) tests membership, x | (1 << i) adds, x & (x - 1) clears the lowest set bit and x & -x isolates it. Integer.bitCount is a constant-time population count on fixed-width integers. Bitmask dynamic programming over subsets costs O(2^k · k) for k items, which is practical only for small k around 20. Remember that Java shifts use the low five bits of the shift distance for int.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
static int[] prefixFunction(String p) {
int[] border = new int[p.length()];
for (int i = 1, k = 0; i < p.length(); i++) {
while (k > 0 && p.charAt(i) != p.charAt(k)) k = border[k - 1];
if (p.charAt(i) == p.charAt(k)) k++;
border[i] = k;
}
return border;
}
static int indexOf(String text, String p) {
if (p.isEmpty()) return 0;
int[] border = prefixFunction(p);
for (int i = 0, k = 0; i < text.length(); i++) {
while (k > 0 && text.charAt(i) != p.charAt(k)) k = border[k - 1];
if (text.charAt(i) == p.charAt(k)) k++;
if (k == p.length()) return i - k + 1;
}
return -1;
}Walkthrough
For pattern ababc the border array is [0, 0, 1, 2, 0]. Searching ababababc, the matcher reaches k = 4 (abab), mismatches on a versus c, and falls back to border[3] = 2 instead of zero, because ab is already known to match. The inner while loop looks nested, but k rises by at most one per text character and every fallback lowers it, so total fallbacks are bounded by n.
Practice it yourself
Use the prefix function to decide whether a string s is a repetition of a shorter block, such as abcabcabc. State the cost.
Check your reasoning
Compute border for s and let p = n − border[n − 1]. s is a repetition exactly when border[n − 1] > 0 and n % p == 0; the block is s.substring(0, p). For abcabcabc, border[8] = 6, p = 3 and 9 % 3 == 0. It runs in O(n) time and O(n) space for the border array.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.