Efficient Algorithms Implementation | Dataford Interview Questions

Your question is Efficient Algorithms Implementation. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Akamai edge logic may need to detect a token in a request path before applying a Property Manager rule. Given a text string and a pattern string, return the index of the pattern's first occurrence in the text, or -1 if it does not occur.

Implement the search without using Python's built-in substring search methods. Your solution should preprocess the pattern so repeated prefixes are not rescanned.

Formal Specification

Implement find_token(text, pattern):

Input: two strings, text and pattern.
Output: an integer containing the smallest index where pattern begins in text, or -1 when no match exists.
An empty pattern should return 0, following standard substring-search conventions.

Constraints

0 <= len(text) <= 10^6
0 <= len(pattern) <= 10^5
Both strings contain ASCII characters
Return the first occurrence only
An empty pattern returns 0

Function Signature

def find_token(text, pattern):