Rosalind最长公共子串问题代码修复求助

Let's break down the issues in your code and fix them step by step!

1. File Reading Problems #

Your current file handling has two critical flaws that mess up your input sequences:

• You didn't remove newline characters (\n) from sequence lines, so your final sequences will include these invisible characters. This makes substring checks fail because other sequences don't contain \n.
• You didn't properly merge multi-line sequences. For example, if a single DNA sequence spans 3 lines, your code adds each line as a separate element to strs — while join can glue them back together, the leftover newlines break the data.

Here's the fixed file reading code:

sequences = []
current_sequence = ""

with open("rosalind_lcsm.txt", "r") as rosa:
    for line in rosa:
        stripped_line = line.strip()  # Remove newlines and extra whitespace
        if not stripped_line:
            continue  # Skip empty lines
        if stripped_line.startswith(">"):
            # Save the completed sequence when hitting a new sequence header
            if current_sequence:
                sequences.append(current_sequence)
                current_sequence = ""
        else:
            # Append line content to the current sequence
            current_sequence += stripped_line
    # Don't forget to add the last sequence after the loop ends
    if current_sequence:
        sequences.append(current_sequence)

This code will collect each full DNA sequence as a clean, newline-free string in the sequences list.

2. Broken Substring Search Logic #

Your core search logic has a major flaw: you don't check all possible starting positions in the reference sequence. Instead, you jump the start pointer forward in large steps, which skips over many potential longer common substrings.

For example, if your reference sequence is ABABC, your code would check A, AB, ABA (then stop), then jump to start at position 3 — completely missing the common substring BAB starting at position 1.

Improved Search Approach

A more efficient and correct strategy is:

1. Use the shortest sequence as your reference (since the longest common substring can't be longer than the shortest sequence in the set).
2. Check substrings starting from the longest possible length downwards. The first substring you find that exists in all sequences is your answer (no need to check shorter lengths after that).

Here's the fixed search function:

def find_longest_common_substring(sequences):
    # Pick the shortest sequence to minimize unnecessary checks
    shortest_seq = min(sequences, key=len)
    max_possible_length = len(shortest_seq)
    
    # Check from longest to shortest substrings
    for length in range(max_possible_length, 0, -1):
        # Iterate all possible starting positions for this substring length
        for start in range(max_possible_length - length + 1):
            candidate_substring = shortest_seq[start:start+length]
            # Verify if this substring exists in every sequence
            if all(candidate_substring in seq for seq in sequences):
                return candidate_substring
    return ""  # The problem guarantees a common substring, so this is a fallback

Full Working Code #

Combine the two parts for a complete solution:

def find_longest_common_substring(sequences):
    shortest_seq = min(sequences, key=len)
    max_possible_length = len(shortest_seq)
    
    for length in range(max_possible_length, 0, -1):
        for start in range(max_possible_length - length + 1):
            candidate_substring = shortest_seq[start:start+length]
            if all(candidate_substring in seq for seq in sequences):
                return candidate_substring
    return ""

# Read and process input file
sequences = []
current_sequence = ""

with open("rosalind_lcsm.txt", "r") as rosa:
    for line in rosa:
        stripped_line = line.strip()
        if not stripped_line:
            continue
        if stripped_line.startswith(">"):
            if current_sequence:
                sequences.append(current_sequence)
                current_sequence = ""
        else:
            current_sequence += stripped_line
    if current_sequence:
        sequences.append(current_sequence)

# Find and print the result
print(find_longest_common_substring(sequences))

Why This Works #

• Clean Input: The file reader ensures all sequences are pure ACGT strings with no extra characters.
• Efficient Search: By starting with the longest possible substrings and using the shortest sequence as a reference, we avoid wasting time checking impossible lengths. We also check every possible starting position, so no valid substring is missed.

内容的提问来源于stack exchange，提问作者Fırat Uyulur