Python实现longest函数：求解字符串首尾最长重复子串长度

Hey there! Let's work through this problem step by step to build a clean, reliable solution. First, let's clarify the core requirement from your description and test cases: we need a Python function longest that returns the length of the longest substring that appears at both the start and end of the input string, with an extra rule: this substring must be consecutively repeated either at the start or the end (which explains test cases like longest('121') returning 0).

Why Your Previous Attempts Failed #

• Regex approach: The KeyError likely came from trying to access a regex capture group that didn't match for edge cases like '12112'. Regex gets cumbersome here because we need to check all possible substring lengths, not just a fixed pattern.
• Modified third-party code: If it returned 1 for cases that should return 3, 4, or 6, it probably wasn't checking from the longest possible substring downwards—so it stopped at the first small match instead of finding the longest valid one.

Elegant Solution #

Here's a straightforward, efficient approach that aligns perfectly with your test cases:

def longest(s):
    """Return the length of the longest substring present at both start and end of the string,
    where the substring is consecutively repeated at either the start or end.
    
    >>> longest('1211')
    1
    >>> longest('1212')
    2
    >>> longest('212111212112112121222222212212112121')
    2
    >>> longest('1')
    0
    >>> longest('121')
    0
    >>> longest('12112')
    0
    """
    n = len(s)
    # The longest possible candidate can't exceed half the string length (avoids overlap issues)
    max_possible_length = n // 2
    
    for length in range(max_possible_length, 0, -1):
        # Check if the substring exists at both start and end
        prefix = s[:length]
        suffix = s[-length:]
        
        if prefix == suffix:
            # Verify the substring is consecutively repeated at start OR end
            has_start_repeat = (length * 2 <= n) and (s[:length*2] == prefix * 2)
            has_end_repeat = (length * 2 <= n) and (s[-length*2:] == suffix * 2)
            
            if has_start_repeat or has_end_repeat:
                return length
    return 0

How This Code Works #

1. Start with the longest possible substring: We begin checking from half the input string's length (since a consecutive repeat can't be longer than this without overlapping).
2. Check for matching prefix and suffix: For each length, we first confirm the substring exists at both the start and end of the string.
3. Verify consecutive repetition: We then check if this substring is repeated consecutively either at the start (like '12' in '1212') or at the end (like '1' in '1211').
4. Return early: As soon as we find the longest valid substring, we return its length immediately—no need to check shorter lengths.
5. Handle edge cases: If no valid substring is found (or the input string is too short), we return 0.

This approach is efficient (returns early in most cases) and easy to read, making it simple to adjust if your rules need tweaking later.

内容的提问来源于stack exchange，提问作者Jirka