Longest proper prefix that is also a suffix

Given a string s, return the length of the longest string that is both a proper prefix and a proper suffix of s.

• A prefix is a run of characters at the start of s; a suffix is a run at the end.
• Proper means the whole string does not count. So the answer is always less than len(s).
• The prefix and the suffix may overlap inside s.
• If no such non-empty string exists, return 0.

Implement:

def longest_prefix_suffix(s: str) -> int: ...

Constraints

• 0 <= len(s) <= 10^5
• s contains lowercase English letters.
• Aim for better than O(n^2) time.

Examples

Example 1

Input:  s = "abcabcab"
Output: 5

"abcab" is the first five characters and also the last five. The two copies overlap in the middle.

Example 2

Input:  s = "pqrs"
Output: 0

No non-empty proper prefix matches the suffix of the same length.