Introduction

A border of a string is a non-empty substring that is both a proper prefix and a proper suffix. Finding the longest border matters in pattern matching and repetition analysis because it tells you how much structure the string shares with itself.

Naive Idea First

The direct approach is to test every possible border length from longest to shortest. For a string s, you compare s[:k] with s[-k:] until you find the largest match.

That is easy to understand:

1def longest_border_naive(s: str) -> str:
2    for k in range(len(s) - 1, 0, -1):
3        if s[:k] == s[-k:]:
4            return s[:k]
5    return ""
6
7print(longest_border_naive("abcab"))      # ab
8print(longest_border_naive("aaaa"))       # aaa
9print(longest_border_naive("abcdef"))     # empty string

The problem is runtime. Comparing slices repeatedly can make this approach quadratic in the worst case.

The Efficient Approach: Prefix Function

The standard linear-time solution uses the prefix function from the Knuth-Morris-Pratt algorithm. For each position, the prefix function stores the length of the longest proper prefix that is also a suffix for the substring ending at that position.

Once you compute that array for the full string, the last value is exactly the length of the longest border of the whole string.

1def prefix_function(s: str) -> list[int]:
2    pi = [0] * len(s)
3
4    for i in range(1, len(s)):
5        j = pi[i - 1]
6
7        while j > 0 and s[i] != s[j]:
8            j = pi[j - 1]
9
10        if s[i] == s[j]:
11            j += 1
12
13        pi[i] = j
14
15    return pi
16
17def longest_border(s: str) -> str:
18    if not s:
19        return ""
20
21    pi = prefix_function(s)
22    border_length = pi[-1]
23    return s[:border_length]
24
25print(longest_border("abcab"))   # ab
26print(longest_border("aaaa"))    # aaa
27print(longest_border("abacaba")) # aba

This runs in O(n) time and O(n) space.

Why the Prefix Function Works

Suppose the string is "abacaba". The longest border is "aba". The prefix-function array tracks how much prefix information survives as you scan left to right. When characters stop matching, the algorithm does not restart from zero blindly. Instead, it jumps to the next possible border length that was already computed.

That reuse of previously known borders is why KMP is fast. It avoids repeating work the naive approach would perform again and again.

Returning the Length Instead of the String

In many interview and competitive-programming problems, you only need the border length:

1def longest_border_length(s: str) -> int:
2    if not s:
3        return 0
4    return prefix_function(s)[-1]
5
6print(longest_border_length("abcab"))  # 2

The actual border text is then s[:length].

Finding All Borders

The prefix-function array also lets you recover every border, not just the longest one. Starting from the final prefix value, repeatedly follow the prefix links:

1def all_borders(s: str) -> list[str]:
2    if not s:
3        return []
4
5    pi = prefix_function(s)
6    borders = []
7    k = pi[-1]
8
9    while k > 0:
10        borders.append(s[:k])
11        k = pi[k - 1]
12
13    return borders[::-1]
14
15print(all_borders("aaaa"))  # ['a', 'aa', 'aaa']

This is a useful extension when the problem asks about repeated structure rather than only the maximum border.

Common Pitfalls

• Forgetting that a border must be proper, so the entire string does not count.
• Using repeated slicing in the naive approach and underestimating the performance cost.
• Confusing prefix function with suffix arrays or other unrelated string structures.
• Mishandling the empty-string case.
• Returning the border length when the problem expects the substring itself, or vice versa.

Summary

• A border is a substring that is both a proper prefix and a proper suffix.
• The naive approach is simple but can take quadratic time.
• The KMP prefix function gives the longest border in linear time.
• The last prefix-function value is the border length for the whole string.
• The same array can also be used to recover all borders, not just the longest one.