Win10环境下Python 3.9.6长文本（64字符及以上）重复子串检测失效问题及解决方案咨询

Alright, let's break down what's wrong with your current code and fix it step by step. First, we'll address the core issues, then implement optimized solutions for your actual requirement.

1. What's Broken in the Current Code? #

a. Misaligned Logic with Your Goal #

Your code is trying to find common substrings across all lines (using set intersections), but your stated goal is to detect substrings that repeat at least twice within a text (either within a single line or across multiple lines). This mismatch means even short-line "success" was solving the wrong problem.

b. Efficiency Bottleneck for Long Texts #

Generating every possible substring with nested loops has an O(n²) time complexity. For a 64-character string, that's 2080 substrings; for a 1000-character string, that's 500,500 substrings. This leads to massive memory usage and slow execution for longer inputs, which is why your code fails with 64+ character texts.

Solution 1: Detect Repeats Within a Single Text #

If you want to find substrings that appear at least twice in one piece of text, we'll use a Suffix Automaton (SAM)—an algorithm that runs in linear O(n) time and is designed for efficient substring analysis on long texts.

Step-by-Step Implementation #

class State:
    def __init__(self):
        self.next = {}  # Maps characters to state indices
        self.link = -1  # Link to the suffix state
        self.len = 0    # Length of the longest substring in this state

def build_suffix_automaton(s):
    size = 1
    last = 0
    states = [State()]
    for c in s:
        curr = size
        size += 1
        states.append(State())
        states[curr].len = states[last].len + 1
        p = last
        # Traverse suffix links to update the automaton
        while p != -1 and c not in states[p].next:
            states[p].next[c] = curr
            p = states[p].link
        if p == -1:
            states[curr].link = 0
        else:
            q = states[p].next[c]
            if states[p].len + 1 == states[q].len:
                states[curr].link = q
            else:
                # Clone state q to handle split substrings
                clone = size
                size += 1
                states.append(State())
                states[clone].len = states[p].len + 1
                states[clone].next = states[q].next.copy()
                states[clone].link = states[q].link
                # Update all links pointing to q to point to clone
                while p != -1 and states[p].next.get(c, -1) == q:
                    states[p].next[c] = clone
                    p = states[p].link
                states[q].link = clone
                states[curr].link = clone
        last = curr
    return states

def find_repeated_substrings(text, min_length=1):
    if len(text) < 2 * min_length:
        return set()  # Can't have a repeated substring if text is too short
    
    sam = build_suffix_automaton(text)
    cnt = [0] * len(sam)
    # Topologically sort states by length (descending)
    order = sorted(range(len(sam)), key=lambda x: -sam[x].len)
    
    # Mark terminal states (substrings ending at the text's end)
    u = len(sam) - 1
    while u != -1:
        cnt[u] += 1
        u = sam[u].link
    
    # Propagate occurrence counts to suffix links
    for state_idx in order:
        if sam[state_idx].link != -1:
            cnt[sam[state_idx].link] += cnt[state_idx]
    
    repeated_substrings = set()
    # Extract all substrings that appear at least twice
    for state_idx in range(1, len(sam)):
        if cnt[state_idx] >= 2 and sam[state_idx].len >= min_length:
            # Get the longest substring represented by this state
            longest_sub = text[len(text) - sam[state_idx].len : len(text) - sam[sam[state_idx].link].len]
            # Add all valid shorter substrings in this state's range
            start_len = max(min_length, sam[sam[state_idx].link].len + 1)
            for l in range(start_len, sam[state_idx].len + 1):
                repeated_substrings.add(longest_sub[-l:])
    
    return repeated_substrings

Usage Example #

# Test with a 64-character long text
long_text = "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
repeated = find_repeated_substrings(long_text, min_length=2)
print("Repeated substrings:", repeated)

Solution 2: Detect Repeats Across Multiple Lines #

If you want substrings that appear in at least two different lines, here's an optimized alternative to your original set-intersection approach:

def find_substrings_across_lines(lines, min_length=1):
    substr_line_count = {}
    
    for line in lines:
        # Get all unique substrings from the current line
        line_substrings = set()
        line_len = len(line)
        for l in range(min_length, line_len + 1):
            for i in range(line_len - l + 1):
                substr = line[i:i+l]
                line_substrings.add(substr)
        
        # Track how many lines each substring appears in
        for substr in line_substrings:
            substr_line_count[substr] = substr_line_count.get(substr, 0) + 1
    
    # Filter substrings that appear in 2+ lines
    return {substr for substr, count in substr_line_count.items() if count >= 2}

Why This Is Better #

Instead of generating full substring sets for each line and computing expensive intersections, we directly track occurrence counts. This reduces memory usage and speeds up execution for large input sets.

Key Fixes Recap #

1. Aligned Logic: We now solve your actual requirement (either intra-text or cross-line repeats).
2. Efficiency: The Suffix Automaton handles long texts in linear time, eliminating the O(n²) bottleneck of generating every substring.
3. Memory Optimization: We avoid redundant substring storage and use efficient data structures to track occurrences.

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