Longest Prefix-Suffix Relation | Dataford Interview Questions

Given two strings A and B, what's the longest prefix of A which is suffix of B.

Asked in the phone screen stage. Implement the function below and return the matching substring. If no non-empty match exists, return an empty string. When a matched prefix has a shorter matching border at the end of B, continue with that border, as required by the examples.

Input and Output

A and B are strings. Return a string containing the required prefix of A.

Constraints

0 <= len(A), len(B) <= 10^5
A and B contain standard characters
Return a string
The intended scan is linear in the combined input size

Function Signature

def longest_prefix_suffix(A, B):

Your question is Longest Prefix-Suffix Relation. Start with the requirements in the Question tab.

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

Problem