## Problem Given a text string T and a pattern string P, find all starting indices where P occurs in T. First implement naive O(n*m) search, then implement KMP for O(n+m). ```python def find_pattern_naive(text: str, pattern: str) -> list[int]: pass def build_kmp_table(pattern: str) -> list[int]: # Failure function: kmp_table[i] = length of longest proper prefix # of pattern[0..i] that is also a suffix pass def find_pattern_kmp(text: str, pattern: str) -> list[int]: pass ``` **Example:** ``` find_pattern_kmp("ababcabab", "abab") -> [0, 5] build_kmp_table("abab") -> [0, 0, 1, 2] ``` ## Follow-ups 1. Walk through the KMP failure function construction for pattern "aabaa". 2. How does Rabin-Karp differ from KMP, and when would you prefer it? 3. How would you extend your solution to search for multiple patterns simultaneously? (Aho-Corasick) 4. How would you handle Unicode multi-byte characters in the pattern and text?

InterviewDB Question

String Pattern Detector: Find All Occurrences of a Pattern in a Text Using Efficient String Matching

phone

Question Details

Problem Given a text string T and a pattern string P, find all starting indices where P occurs in T. First implement naive O(n*m) search, then implement KMP for O(n+m). Example: Follow-ups Walk through the KMP failure function construction for patter…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Onsite Phone Strings

More from Verkada

1p3a Verkada Store Front Tech Phone Screen Interview Experience LeetCode #986 Interval List Intersections InterviewDB Camera API: Design an OOP Camera Control API for a Multi-Camera System InterviewDB Camera Intensity: Compute Pixel Intensity Statistics Across a Camera Feed 1p3a Verkada Tech Phone Screen: Camera Failure Aggregation Problem

← All Verkada questions Verkada Software Engineer Questions → All Strings Questions →