Implement string matching with follow-up

Question

Given a text T and a pattern P, implement a function firstIndex(T, P) that returns the starting index of the first occurrence of P in T, or -1 if P does not occur. Aim for O(|T| + |P|) time and O(|P|) extra space.

Be ready to extend the solution through the following follow-ups:

1. Algorithm comparison. Compare the naive (brute-force) approach to KMP and Rabin–Karp. Explain the time and space complexity of each and when you would choose one over another.
2. Robustness. How would you handle Unicode text (multi-byte / combining characters) and very long inputs? Discuss correctness and memory considerations.
3. Edge cases. Walk through the important edge cases: empty pattern, empty text, pattern longer than text, and highly repetitive patterns (e.g. P = "aaaa" in T = "aaaaaa").
4. Wildcards. Extend the matcher to support two wildcard characters in the pattern: ? matches any single character, and * matches any (possibly empty) sequence of characters. Describe the matching semantics and complexity.
5. Multi-pattern search. Extend the solution to search for k patterns P1..Pk in T simultaneously and return all starting indices for each pattern. Outline the data structure you would use and the runtime / space trade-offs versus running a single-pattern matcher k times.

First Occurrence of a Pattern (KMP)

Given a text t and a pattern p, implement solution(t, p) that returns the starting index of the first occurrence of p in t, or -1 if p does not occur. Aim for O(|t| + |p|) time and O(|p|) extra space.

Conventions:

• An empty pattern matches at index 0.
• If p is longer than t, return -1.
• Overlapping is irrelevant for the first occurrence; just return the earliest start index.

Use the Knuth–Morris–Pratt failure (LPS) table so the text pointer never backtracks — this keeps the search linear even on highly repetitive inputs like p = "aaaa" inside t = "aaaaaa", where a naive scan degrades to O(|t|·|p|).

Constraints

• 0 <= |t|, |p|
• Characters are compared by code point (decode to code points for Unicode-correct indexing).
• An empty pattern returns 0.
• If |p| > |t|, return -1.

Examples

Example 1

Input: ("abxabcabcaby", "abcaby")
Output: 6

Explanation: The pattern 'abcaby' first appears starting at index 6.

Example 2

Input: ("hello world", "world")
Output: 6

Explanation: 'world' begins at index 6.

Hints

1. A naive scan is O(|t|·|p|) worst case and blows up on repetitive inputs like 'aaaa' in 'aaaaaa'. You need the text pointer to never move backward.
2. Precompute the LPS (longest proper prefix that is also a suffix) array of the pattern in O(|p|). On a mismatch at pattern position k, fall back to lps[k-1] instead of restarting.
3. Handle the conventions first: empty pattern -> 0, and |p| > |t| -> -1, before building the table.

Wildcard Pattern Matching (? and *)

Follow-up 4. Extend the matcher to support two wildcard characters in the pattern p:

• ? matches any single character.
• * matches any (possibly empty) sequence of characters.

Implement solution(t, p) returning a boolean: does the pattern match the entire text t? This is glob-style (anchored) matching, not substring search.

A single linear scan is insufficient because * can match an arbitrary span — use dynamic programming. dp[i][j] = does p[0..j) match t[0..i).

Constraints

• 0 <= |t|, |p|
• p may contain '?' and '*' wildcards; all other characters are literal.
• Matching is anchored: the whole pattern must match the whole text.
• A run of leading '*' can match the empty prefix.

Examples

Example 1

Input: ("abcde", "a?c*")
Output: True

Explanation: 'a' literal, '?'=b, 'c' literal, '*'=de.

Example 2

Input: ("abcde", "a*e")
Output: True

Explanation: '*' absorbs 'bcd' between the anchors 'a' and 'e'.

Hints

1. '*' makes a single linear scan insufficient — model it with DP: dp[i][j] = does p[0..j) match t[0..i).
2. Base row: dp[0][j] is True only while every pattern char so far is '' (each '' can match the empty string).
3. For '*': dp[i][j] = dp[i-1][j] (star consumes t[i-1]) OR dp[i][j-1] (star matches empty). For '?' or a literal match: dp[i][j] = dp[i-1][j-1].

Multi-Pattern Search (Aho–Corasick)

Follow-up 5. Search for k patterns simultaneously in a single pass over the text.

Implement solution(text, patterns) where patterns is a list of strings. Return a list of lists result such that result[i] is the list of all start indices (in ascending order, including overlapping occurrences) at which patterns[i] occurs in text.

Rules:

• The output order must align with the input pattern order. Duplicate patterns each get their own (identical) result list.
• An empty pattern contributes an empty list.
• Running a single-pattern matcher k times costs O(k·|text| + Σ|Pi|). Build an Aho–Corasick automaton (a trie with KMP-style failure links + output links) to scan the text once: O(Σ|Pi| + |text| + z) where z is the number of reported matches, independent of k for the scan.

Constraints

• 0 <= number of patterns k
• Patterns may repeat; each repeated pattern gets its own result entry.
• Overlapping occurrences are all reported.
• An empty pattern contributes an empty list.

Examples

Example 1

Input: ("ahishers", ["he", "she", "his", "hers"])
Output: [[4], [3], [1], [4]]

Explanation: Classic Aho–Corasick example: 'he'@4, 'she'@3, 'his'@1, 'hers'@4 (overlapping 'he'/'hers' share the same scan).

Example 2

Input: ("aaaa", ["a", "aa"])
Output: [[0, 1, 2, 3], [0, 1, 2]]

Explanation: Overlapping matches: 'a' at every index, 'aa' at 0,1,2.

Hints

1. Running KMP k separate times is O(k·|text| + Σ|Pi|). To scan the text once, generalize KMP's failure function to a trie over all patterns.
2. Build a trie of all patterns, then add failure links via BFS (the longest proper suffix of the current node that is also a prefix in the trie), plus output links so one node can report multiple patterns ending there.
3. Merge each node's output list with its failure node's output list during the BFS so a single position emits every pattern that ends there, including shorter suffixes.

Solution

Single-pattern core is KMP for the O(|T|+|P|) bound; the follow-ups layer on (a) a naive/KMP/Rabin–Karp complexity comparison, (b) Unicode code-point correctness plus streaming for huge inputs, (c) standard edge cases where repetitive patterns expose the naive blowup, (d) DP-based wildcard (?/*) matching, and (e) Aho–Corasick (KMP generalized to a trie with failure links) for simultaneous multi-pattern search, with Rabin–Karp as the equal-length alternative.

1) Core: first occurrence in O(|T| + |P|)

The naive scan is O(|T|·|P|) worst case. To hit O(|T| + |P|) use Knuth–Morris–Pratt (KMP), which precomputes a failure (longest-proper-prefix-that-is-also-suffix) table for P so the text pointer never moves backward.

def build_lps(p):
    lps = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = lps[k - 1]
        if p[i] == p[k]:
            k += 1
        lps[i] = k
    return lps

def first_index(t, p):
    if p == "":
        return 0            # empty pattern matches at index 0 (define convention up front)
    if len(p) > len(t):
        return -1
    lps = build_lps(p)       # O(|P|) time, O(|P|) space
    k = 0
    for i in range(len(t)):  # O(|T|) time, text pointer never backs up
        while k > 0 and t[i] != p[k]:
            k = lps[k - 1]
        if t[i] == p[k]:
            k += 1
        if k == len(p):
            return i - len(p) + 1
    return -1

Total: O(|T| + |P|) time, O(|P|) extra space — meets the bar.

2) Algorithm comparison

Algorithm	Time (worst)	Extra space	Notes
Naive / brute force	O(|T|·|P|)	O(1)	Simple; pathological on repetitive inputs (e.g. aaaa...a + aaab).
KMP	O(|T| + |P|)	O(|P|)	Deterministic linear; no hashing, no false positives. Best default here.
Rabin–Karp	O(|T| + |P|) avg, O(|T|·|P|) worst	O(1)	Rolling polynomial hash; cheap to generalize to multi-pattern (hash a set of patterns of equal length). Worst case is hash-collision degenerate; mitigate with a good base/modulus and verify on hash hits.

Choose KMP when you want a hard linear guarantee for a single pattern; choose Rabin–Karp when matching many same-length patterns or 2-D matching where rolling hashes shine.

3) Unicode and very long inputs

• Operate on code points, not bytes. In a variable-width encoding (UTF-8/UTF-16) indexing raw bytes can split a character and produce false matches. Decode to a sequence of code points (or use a Unicode-aware string type) so |T|/|P| count characters, and the returned index is a character index. State which index convention you return.
• Normalize (e.g. NFC) before comparing if canonically-equivalent sequences (precomposed vs. combining accent) should be treated as equal; otherwise comparison is code-point-exact.
• Very long inputs: KMP is streaming-friendly — it reads T left-to-right once and the text pointer never backtracks, so T can be processed as a stream/chunks while keeping only the O(|P|) LPS table and a single matched-length counter k in memory. This avoids loading all of T at once.

4) Edge cases

• Empty pattern: agree on a convention up front (commonly returns 0).
• Empty text / pattern longer than text: return -1 (no occurrence). Guard before building the table.
• Repetitive patterns (P="aaaa" in T="aaaaaa"): this is exactly where naive blows up but KMP stays linear because the LPS table reuses the partial match instead of restarting.
• Single-character T or P, P == T, and matches at the very start / very end.

5) Wildcards: ? (any single char) and * (any sequence)

This becomes glob-style matching, best solved with dynamic programming (the * makes a single linear scan insufficient).

Let dp[i][j] = does P[0..j) match T[0..i).

• dp[0][0] = True.
• dp[0][j] = dp[0][j-1] if P[j-1] == '*' (a leading run of * can match empty).
• For P[j-1] == '*': dp[i][j] = dp[i-1][j] (star consumes T[i-1]) or dp[i][j-1] (star matches empty).
• For P[j-1] == '?' or P[j-1] == T[i-1]: dp[i][j] = dp[i-1][j-1].
• Else False.

This is O(|T|·|P|) time; space can be reduced to O(|P|) with a rolling row. Note this checks whether the whole pattern matches the whole text; to find a first occurrence within T, anchor the search or wrap the pattern with implicit * at both ends depending on the required semantics — clarify with the interviewer which is wanted. A greedy two-pointer with a backtrack-on-* variant also runs in O(|T|·|P|) worst case but O(1) space.

6) Multi-pattern search: P1..Pk simultaneously

Running KMP k times costs O(k·|T| + Σ|Pi|). To match all patterns in one pass over T, use the Aho–Corasick automaton:

1. Build a trie of all k patterns: O(Σ|Pi|) nodes.
2. Add failure links (BFS), the multi-pattern generalization of KMP's failure function, plus output links so that when one pattern's end is reached you also report every other pattern that is a suffix of the current matched text.
3. Scan T once, following goto/failure links; at each position emit every pattern that ends there.

• Time: O(Σ|Pi| + |T| + z) where z is the total number of matches reported — independent of k for the scan itself.
• Space: O(Σ|Pi|) for the automaton.

Trade-off: Aho–Corasick has higher build cost and memory than a single KMP run, but it wins decisively as k grows because it amortizes the text scan across all patterns. If all patterns share the same length, Rabin–Karp with a hash set of pattern hashes is a simpler alternative: one rolling hash over T, check membership at each window, verify on hits. Return results as a map pattern -> [start indices] (deduplicate occurrences as required).