寻找字符串中重复次数最多的Tandem Repeats（串联重复序列）算法

Got it, let's tackle this problem step by step. First, let's make sure we're on the same page: tandem repeats are consecutive, unbroken repeated character blocks. For example, in ababab, the block ab repeats 3 times; in aaaaa, a repeats 5 times (or aa repeats 2 times, but we care about the highest repeat count here). Unlike finding the most frequent substring, we're focused on which block repeats the most times in a row, not how often it shows up scattered in the string.

Approach #

Here's a straightforward, easy-to-understand approach to solve this:

• Iterate over possible block lengths: The shortest possible block is 1 character, and the longest possible is half the string length (since a block needs to repeat at least twice to count as a tandem repeat).
• Count consecutive repeats for each block length: For each block size, scan the string to find how many times each block repeats consecutively.
• Track the maximum repeat count: Keep track of which blocks have the highest consecutive repeat count (there might be ties, so we'll handle those too).

Python Implementation #

Here's a function that puts this logic into action, with comments explaining each step:

def find_most_tandem_repeats(s):
    if len(s) < 2:
        return []  # No possible tandem repeats in a string shorter than 2 characters
    
    max_repeats = 0
    result = []
    
    # Iterate over all possible block lengths (from 1 to half the string length)
    for block_length in range(1, len(s) // 2 + 1):
        i = 0
        while i <= len(s) - block_length:
            current_block = s[i:i+block_length]
            current_count = 1
            
            # Check consecutive repeats of the current block
            while (i + block_length <= len(s) - block_length) and (s[i+block_length:i+2*block_length] == current_block):
                current_count += 1
                i += block_length  # Move to the next block position
            
            # Update our result if we found a higher repeat count
            if current_count > max_repeats:
                max_repeats = current_count
                result = [(current_block, current_count)]
            # If it's equal to the max, add it to the result (handle ties)
            elif current_count == max_repeats and current_count > 1:
                if (current_block, current_count) not in result:
                    result.append((current_block, current_count))
            
            i += 1  # Move to the next starting position
    
    return result

Testing the Function #

Let's test this with some examples to see how it works:

Example 1: Multiple blocks with the same max repeats #

s = "abababcccccc"
print(find_most_tandem_repeats(s))  # Output: [('ab', 3), ('cc', 3)]

Here, ab repeats 3 times in a row, and cc also repeats 3 times—both are valid since they have the highest count.

Example 2: Single character repeated many times #

s = "aaaaa"
print(find_most_tandem_repeats(s))  # Output: [('a', 5)]

The block a repeats 5 times consecutively, which is the highest possible.

Example 3: Partial repeats don't count #

s = "abcabcab"
print(find_most_tandem_repeats(s))  # Output: [('abc', 2)]

abc repeats twice, but the remaining ab isn't a full repeat of the block, so it doesn't add to the count.

Example 4: No tandem repeats #

s = "abcd"
print(find_most_tandem_repeats(s))  # Output: []

None of the blocks repeat consecutively, so we return an empty list.

Notes on Optimization #

This approach is easy to understand and works well for most practical cases. If you're dealing with extremely long strings (like thousands of characters), you could optimize it using suffix arrays or other more advanced algorithms, but for most use cases, this implementation will be more than sufficient.

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