Longest Common Subsequence: Introduction to 2D Dynamic Programming

def lcs_analysis():
    """
    Complete analysis of the LCS problem
    """
    
    # Problem Understanding
    """
    Input: Two strings X and Y
    Output: Length of longest common subsequence
    
    Example:
    X = "ABCDGH"
    Y = "AEDFHR"
    LCS = "ADH" (length 3)
    """
    
    # State Definition
    """
    dp[i][j] = LCS length for X[0:i] and Y[0:j]
    
    i ranges from 0 to len(X)
    j ranges from 0 to len(Y)
    """
    
    # Recurrence Relation
    """
    If X[i-1] == Y[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
    Else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    """
    
    # Base Cases
    """
    dp[0][j] = 0 for all j (empty X with any Y)
    dp[i][0] = 0 for all i (any X with empty Y)
    """

def lcs_basic_implementation(X, Y):
    """
    Basic LCS implementation using 2D tabulation
    Time: O(m*n), Space: O(m*n)
    """
    m, n = len(X), len(Y)
    
    # Create DP table with extra row and column for base cases
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                # Characters match: extend previous LCS
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # Characters don't match: take best from either direction
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

def lcs_with_detailed_trace(X, Y):
    """
    LCS implementation with step-by-step trace
    """
    print(f"Finding LCS of '{X}' and '{Y}'")
    m, n = len(X), len(Y)
    
    # Create and initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Print initial table
    print("\nInitial DP table:")
    print_dp_table(dp, X, Y)
    
    # Fill the table with detailed logging
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                print(f"\nMatch at ({i},{j}): '{X[i-1]}' == '{Y[j-1]}'")
                print(f"dp[{i}][{j}] = dp[{i-1}][{j-1}] + 1 = {dp[i-1][j-1]} + 1 = {dp[i][j]}")
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                print(f"\nNo match at ({i},{j}): '{X[i-1]}' != '{Y[j-1]}'")
                print(f"dp[{i}][{j}] = max(dp[{i-1}][{j}], dp[{i}][{j-1}]) = max({dp[i-1][j]}, {dp[i][j-1]}) = {dp[i][j]}")
    
    print("\nFinal DP table:")
    print_dp_table(dp, X, Y)
    
    return dp[m][n]

def print_dp_table(dp, X, Y):
    """Helper function to print DP table in readable format"""
    print("    ", end="")
    print("  ".join(f"{c:2s}" for c in [" "] + list(Y)))
    
    for i, row in enumerate(dp):
        row_char = " " if i == 0 else X[i-1]
        print(f"{row_char:2s} ", end="")
        print("  ".join(f"{val:2d}" for val in row))

def lcs_with_reconstruction(X, Y):
    """
    Find LCS and reconstruct the actual subsequence
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Reconstruct LCS by backtracking
    lcs_sequence = []
    i, j = m, n
    
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            # This character is part of LCS
            lcs_sequence.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            # LCS came from above
            i -= 1
        else:
            # LCS came from left
            j -= 1
    
    # Reverse since we built it backwards
    lcs_sequence.reverse()
    
    return dp[m][n], ''.join(lcs_sequence)

def lcs_all_solutions(X, Y):
    """
    Find all possible LCS (when multiple exist)
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # Find all LCS using recursive backtracking
    def find_all_lcs(i, j, current_lcs):
        if i == 0 or j == 0:
            all_lcs.append(current_lcs[::-1])  # Reverse the sequence
            return
        
        if X[i-1] == Y[j-1]:
            # This character must be in LCS
            current_lcs.append(X[i-1])
            find_all_lcs(i-1, j-1, current_lcs)
            current_lcs.pop()
        else:
            # Explore both directions if they have same value
            if dp[i-1][j] == dp[i][j]:
                find_all_lcs(i-1, j, current_lcs)
            if dp[i][j-1] == dp[i][j]:
                find_all_lcs(i, j-1, current_lcs)
    
    all_lcs = []
    find_all_lcs(m, n, [])
    
    # Remove duplicates and return
    unique_lcs = list(set(''.join(lcs) for lcs in all_lcs))
    return dp[m][n], unique_lcs

def lcs_space_optimized(X, Y):
    """
    Space-optimized LCS using only O(min(m,n)) space
    Time: O(m*n), Space: O(min(m,n))
    """
    # Ensure Y is the shorter string for optimal space usage
    if len(X) < len(Y):
        X, Y = Y, X
    
    m, n = len(X), len(Y)
    
    # Only need current and previous row
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        
        # Swap rows for next iteration
        prev, curr = curr, prev
    
    return prev[n]

def lcs_space_optimized_with_path(X, Y):
    """
    Space-optimized version that can still reconstruct path
    Uses divide-and-conquer approach
    """
    def lcs_length_with_middle(X, Y):
        """Find LCS length and the middle column values"""
        m, n = len(X), len(Y)
        
        if m == 0 or n == 0:
            return 0, [0] * (n + 1)
        
        # Compute LCS lengths for first half of X
        prev = [0] * (n + 1)
        for i in range(m // 2):
            curr = [0] * (n + 1)
            for j in range(1, n + 1):
                if X[i] == Y[j-1]:
                    curr[j] = prev[j-1] + 1
                else:
                    curr[j] = max(prev[j], curr[j-1])
            prev = curr
        
        # Compute LCS lengths for second half of X (in reverse)
        succ = [0] * (n + 1)
        for i in range(m - 1, m // 2 - 1, -1):
            curr = [0] * (n + 1)
            for j in range(n - 1, -1, -1):
                if X[i] == Y[j]:
                    curr[j] = succ[j+1] + 1
                else:
                    curr[j] = max(succ[j], curr[j+1])
            succ = curr
        
        # Find optimal split point
        total_lcs = 0
        split_j = 0
        for j in range(n + 1):
            if prev[j] + succ[j] > total_lcs:
                total_lcs = prev[j] + succ[j]
                split_j = j
        
        return total_lcs, split_j
    
    def lcs_divide_conquer(X, Y):
        """Divide and conquer LCS reconstruction"""
        if len(X) == 0:
            return ""
        if len(Y) == 0:
            return ""
        if len(X) == 1:
            return X if X in Y else ""
        
        mid = len(X) // 2
        length, split_j = lcs_length_with_middle(X, Y)
        
        # Recursively solve subproblems
        left_lcs = lcs_divide_conquer(X[:mid], Y[:split_j])
        right_lcs = lcs_divide_conquer(X[mid:], Y[split_j:])
        
        return left_lcs + right_lcs
    
    return lcs_divide_conquer(X, Y)

def longest_common_substring(X, Y):
    """
    Find longest common substring (contiguous characters)
    Different from LCS - requires consecutive matching
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    max_length = 0
    ending_pos_i = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    ending_pos_i = i
            else:
                dp[i][j] = 0  # Reset for substring requirement
    
    # Extract the actual substring
    start_pos = ending_pos_i - max_length
    substring = X[start_pos:ending_pos_i]
    
    return max_length, substring

def lcs_three_sequences(X, Y, Z):
    """
    LCS for three sequences - extends to 3D DP
    """
    m, n, p = len(X), len(Y), len(Z)
    
    # 3D DP table
    dp = [[[0 for _ in range(p + 1)] for _ in range(n + 1)] for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            for k in range(1, p + 1):
                if X[i-1] == Y[j-1] == Z[k-1]:
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1
                else:
                    dp[i][j][k] = max(
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    )
    
    return dp[m][n][p]

def lcs_with_wildcards(X, Y, wildcard='*'):
    """
    LCS where wildcard characters match any character
    """
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1] or X[i-1] == wildcard or Y[j-1] == wildcard:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

def dna_sequence_alignment():
    """
    Real-world application: DNA sequence alignment using LCS
    """
    
    def analyze_dna_similarity(seq1, seq2):
        """
        Analyze similarity between two DNA sequences
        """
        print(f"Analyzing DNA sequences:")
        print(f"Sequence 1: {seq1}")
        print(f"Sequence 2: {seq2}")
        
        lcs_length, lcs_sequence = lcs_with_reconstruction(seq1, seq2)
        
        # Calculate similarity metrics
        max_length = max(len(seq1), len(seq2))
        similarity_ratio = lcs_length / max_length if max_length > 0 else 0
        
        print(f"\nResults:")
        print(f"LCS length: {lcs_length}")
        print(f"LCS sequence: {lcs_sequence}")
        print(f"Similarity ratio: {similarity_ratio:.2%}")
        
        # Find differences
        differences = find_sequence_differences(seq1, seq2, lcs_sequence)
        print(f"Mutations detected: {len(differences)}")
        for diff in differences:
            print(f"  {diff}")
        
        return lcs_length, lcs_sequence, similarity_ratio
    
    def find_sequence_differences(seq1, seq2, lcs):
        """
        Find insertions, deletions, and substitutions
        """
        differences = []
        
        # This is a simplified difference detection
        # In practice, you'd use more sophisticated alignment algorithms
        
        i1 = i2 = lcs_idx = 0
        
        while i1 < len(seq1) or i2 < len(seq2):
            if (lcs_idx < len(lcs) and 
                i1 < len(seq1) and 
                i2 < len(seq2) and 
                seq1[i1] == seq2[i2] == lcs[lcs_idx]):
                # Match found
                i1 += 1
                i2 += 1
                lcs_idx += 1
            elif i1 < len(seq1) and (i2 >= len(seq2) or seq1[i1] != seq2[i2]):
                # Deletion in seq2 (or insertion in seq1)
                differences.append(f"Position {i1}: '{seq1[i1]}' deleted")
                i1 += 1
            elif i2 < len(seq2):
                # Insertion in seq2 (or deletion in seq1)
                differences.append(f"Position {i2}: '{seq2[i2]}' inserted")
                i2 += 1
        
        return differences
    
    # Test with sample DNA sequences
    dna1 = "AGCTGACGTACG"
    dna2 = "AGTCGACCGTACG"
    
    analyze_dna_similarity(dna1, dna2)
    
    print("\n" + "="*50)
    
    # Test with more divergent sequences
    dna3 = "ATCGATCG"
    dna4 = "TAGCTAGC"
    
    analyze_dna_similarity(dna3, dna4)

dna_sequence_alignment()

def file_diff_algorithm():
    """
    Implementation of diff-like algorithm using LCS
    """
    
    def compute_file_diff(lines1, lines2):
        """
        Compute differences between two files (represented as line lists)
        """
        lcs_length = lcs_basic_implementation(lines1, lines2)
        
        # Reconstruct the diff
        m, n = len(lines1), len(lines2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Fill DP table
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if lines1[i-1] == lines2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        # Generate diff operations
        diff_operations = []
        i, j = m, n
        
        while i > 0 or j > 0:
            if i > 0 and j > 0 and lines1[i-1] == lines2[j-1]:
                # Lines match
                diff_operations.append(('MATCH', i-1, j-1, lines1[i-1]))
                i -= 1
                j -= 1
            elif i > 0 and (j == 0 or dp[i-1][j] >= dp[i][j-1]):
                # Line deleted from file1
                diff_operations.append(('DELETE', i-1, -1, lines1[i-1]))
                i -= 1
            else:
                # Line added to file2
                diff_operations.append(('ADD', -1, j-1, lines2[j-1]))
                j -= 1
        
        diff_operations.reverse()
        return diff_operations
    
    def print_diff(diff_operations):
        """
        Print diff in a readable format
        """
        for op, line1, line2, content in diff_operations:
            if op == 'MATCH':
                print(f"  {content}")
            elif op == 'DELETE':
                print(f"- {content}")
            elif op == 'ADD':
                print(f"+ {content}")
    
    # Test with sample files
    file1_lines = [
        "def hello_world():",
        "    print('Hello, World!')",
        "    return True",
        "",
        "if __name__ == '__main__':",
        "    hello_world()"
    ]
    
    file2_lines = [
        "def hello_world():",
        "    print('Hello, Universe!')",
        "    print('Welcome!')",
        "    return True",
        "",
        "if __name__ == '__main__':",
        "    hello_world()"
    ]
    
    print("File Diff Analysis:")
    print("=" * 40)
    
    diff_ops = compute_file_diff(file1_lines, file2_lines)
    print_diff(diff_ops)
    
    # Statistics
    matches = sum(1 for op, _, _, _ in diff_ops if op == 'MATCH')
    deletions = sum(1 for op, _, _, _ in diff_ops if op == 'DELETE')
    additions = sum(1 for op, _, _, _ in diff_ops if op == 'ADD')
    
    print(f"\nStatistics:")
    print(f"Lines matched: {matches}")
    print(f"Lines deleted: {deletions}")
    print(f"Lines added: {additions}")
    print(f"Similarity: {matches / max(len(file1_lines), len(file2_lines)):.1%}")

file_diff_algorithm()

def plagiarism_detection():
    """
    Use LCS for basic plagiarism detection
    """
    
    def detect_similarity(text1, text2, min_similarity=0.5):
        """
        Detect potential plagiarism based on LCS similarity
        """
        # Convert texts to word lists for better granularity
        words1 = text1.lower().split()
        words2 = text2.lower().split()
        
        lcs_length, lcs_words = lcs_with_reconstruction(words1, words2)
        
        # Calculate similarity metrics
        total_words = max(len(words1), len(words2))
        similarity = lcs_length / total_words if total_words > 0 else 0
        
        is_plagiarism = similarity >= min_similarity
        
        return {
            'similarity': similarity,
            'is_plagiarism': is_plagiarism,
            'common_length': lcs_length,
            'common_sequence': lcs_words,
            'total_words_1': len(words1),
            'total_words_2': len(words2)
        }
    
    def highlight_common_parts(text1, text2):
        """
        Highlight common parts in both texts
        """
        words1 = text1.split()
        words2 = text2.split()
        
        lcs_length, lcs_sequence = lcs_with_reconstruction(words1, words2)
        lcs_words = lcs_sequence.split()
        
        # Simple highlighting (in practice, you'd use more sophisticated alignment)
        highlighted1 = []
        highlighted2 = []
        
        lcs_idx = 0
        for word in words1:
            if lcs_idx < len(lcs_words) and word.lower() == lcs_words[lcs_idx].lower():
                highlighted1.append(f"**{word}**")
                lcs_idx += 1
            else:
                highlighted1.append(word)
        
        lcs_idx = 0
        for word in words2:
            if lcs_idx < len(lcs_words) and word.lower() == lcs_words[lcs_idx].lower():
                highlighted2.append(f"**{word}**")
                lcs_idx += 1
            else:
                highlighted2.append(word)
        
        return ' '.join(highlighted1), ' '.join(highlighted2)
    
    # Test cases
    original_text = "The quick brown fox jumps over the lazy dog in the garden"
    
    test_cases = [
        ("High similarity", "The quick brown fox leaps over the lazy dog in the yard"),
        ("Medium similarity", "A fast brown fox jumps over a sleeping dog"),
        ("Low similarity", "The cat runs through the house quickly"),
        ("Reordered", "In the garden the lazy dog sees a quick brown fox jumping")
    ]
    
    print("Plagiarism Detection Results:")
    print("=" * 50)
    
    for name, test_text in test_cases:
        result = detect_similarity(original_text, test_text)
        
        print(f"\n{name}:")
        print(f"Text: {test_text}")
        print(f"Similarity: {result['similarity']:.1%}")
        print(f"Plagiarism detected: {'Yes' if result['is_plagiarism'] else 'No'}")
        print(f"Common words: {result['common_length']}")
        
        if result['similarity'] > 0.3:  # Show highlighting for significant similarity
            h1, h2 = highlight_common_parts(original_text, test_text)
            print(f"Original highlighted: {h1}")
            print(f"Test highlighted: {h2}")

plagiarism_detection()

def lcs_with_scores(X, Y, score_matrix):
    """
    LCS with custom scoring for character matches
    
    Args:
        X, Y: input strings
        score_matrix: dict mapping (char1, char2) -> score
    
    Returns:
        maximum score achievable
    """
    # Your implementation here
    pass

def create_dna_scoring_matrix():
    """
    Create scoring matrix for DNA sequences
    +2 for match, -1 for mismatch
    """
    bases = 'ATCG'
    score_matrix = {}
    
    for b1 in bases:
        for b2 in bases:
            score_matrix[(b1, b2)] = 2 if b1 == b2 else -1
    
    return score_matrix

# Test case
X = "ATCG"
Y = "AGTC" 
scores = create_dna_scoring_matrix()
result = lcs_with_scores(X, Y, scores)
print(f"Maximum score: {result}")

def lcs_with_scores(X, Y, score_matrix):
    m, n = len(X), len(Y)
    dp = [[float('-inf')] * (n + 1) for _ in range(m + 1)]
    
    # Base cases: empty sequences have score 0
    for i in range(m + 1):
        dp[i][0] = 0
    for j in range(n + 1):
        dp[0][j] = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # Option 1: Match/mismatch characters
            match_score = score_matrix.get((X[i-1], Y[j-1]), 0)
            dp[i][j] = dp[i-1][j-1] + match_score
            
            # Option 2: Skip character in X (deletion)
            dp[i][j] = max(dp[i][j], dp[i-1][j])
            
            # Option 3: Skip character in Y (insertion)
            dp[i][j] = max(dp[i][j], dp[i][j-1])
    
    return dp[m][n]

code1 = """
for i in range(n):
    sum += arr[i]
    if arr[i] > max_val:
        max_val = arr[i]
"""

code2 = """
for j in range(size):
    total += data[j]
    if data[j] > maximum:
        maximum = data[j]
"""

def debug_lcs():
    """
    Debugging techniques for LCS problems
    """
    
    def validate_lcs_result(X, Y, claimed_lcs):
        """Validate that a claimed LCS is actually valid"""
        # Check if it's a subsequence of both strings
        def is_subsequence(seq, text):
            i = 0
            for char in text:
                if i < len(seq) and char == seq[i]:
                    i += 1
            return i == len(seq)
        
        if not is_subsequence(claimed_lcs, X):
            return False, f"'{claimed_lcs}' is not a subsequence of '{X}'"
        
        if not is_subsequence(claimed_lcs, Y):
            return False, f"'{claimed_lcs}' is not a subsequence of '{Y}'"
        
        return True, "Valid LCS"
    
    def trace_lcs_computation(X, Y):
        """Step-by-step trace for debugging"""
        m, n = len(X), len(Y)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if X[i-1] == Y[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    print(f"Match at ({i},{j}): {X[i-1]} -> dp[{i}][{j}] = {dp[i][j]}")
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                    print(f"No match at ({i},{j}): max({dp[i-1][j]}, {dp[i][j-1]}) = {dp[i][j]}")
        
        return dp[m][n]
    
    def compare_implementations(X, Y):
        """Compare different LCS implementations for consistency"""
        basic_result = lcs_basic_implementation(X, Y)
        optimized_result = lcs_space_optimized(X, Y)
        
        if basic_result != optimized_result:
            print(f"ERROR: Basic={basic_result}, Optimized={optimized_result}")
            return False
        
        print(f"All implementations agree: LCS length = {basic_result}")
        return True

# Test debugging functions
debug_lcs()

def lcs_optimizations():
    """
    Performance optimization techniques for LCS
    """
    
    def early_termination_lcs(X, Y):
        """LCS with early termination optimizations"""
        # If one string is much shorter, maximum LCS is bounded
        min_len = min(len(X), len(Y))
        
        # Quick check for identical strings
        if X == Y:
            return len(X)
        
        # If strings share no common characters, LCS is 0
        set_X = set(X)
        set_Y = set(Y)
        if set_X.isdisjoint(set_Y):
            return 0
        
        # Standard LCS with bounds checking
        return lcs_basic_implementation(X, Y)
    
    def lcs_with_memoization(X, Y):
        """Memoized LCS for comparison with tabulation"""
        memo = {}
        
        def lcs_memo(i, j):
            if i == 0 or j == 0:
                return 0
            
            if (i, j) in memo:
                return memo[(i, j)]
            
            if X[i-1] == Y[j-1]:
                result = lcs_memo(i-1, j-1) + 1
            else:
                result = max(lcs_memo(i-1, j), lcs_memo(i, j-1))
            
            memo[(i, j)] = result
            return result
        
        return lcs_memo(len(X), len(Y))
    
    def parallel_lcs_hint():
        """
        Hint for parallelizing LCS computation
        (Implementation would require threading/multiprocessing)
        """
        print("Parallelization strategies:")
        print("1. Diagonal computation - elements on same diagonal can be computed in parallel")
        print("2. Block-wise computation - divide DP table into blocks")
        print("3. Divide and conquer - split problem recursively")

lcs_optimizations()

def professional_lcs_framework():
    """
    Professional framework for LCS and 2D DP problems
    """
    
    class SequenceComparator:
        def __init__(self, optimization_level=1):
            self.optimization_level = optimization_level
            self.cache = {}
        
        def lcs_length(self, seq1, seq2, use_cache=True):
            """Find LCS length with various optimizations"""
            if use_cache:
                key = (seq1, seq2)
                if key in self.cache:
                    return self.cache[key]
            
            if self.optimization_level >= 2:
                result = self._lcs_space_optimized(seq1, seq2)
            else:
                result = self._lcs_basic(seq1, seq2)
            
            if use_cache:
                self.cache[key] = result
            
            return result
        
        def _lcs_basic(self, X, Y):
            """Basic O(mn) space implementation"""
            return lcs_basic_implementation(X, Y)
        
        def _lcs_space_optimized(self, X, Y):
            """Space-optimized O(min(m,n)) implementation"""
            return lcs_space_optimized(X, Y)
        
        def similarity_score(self, seq1, seq2):
            """Calculate similarity as percentage"""
            lcs_len = self.lcs_length(seq1, seq2)
            max_len = max(len(seq1), len(seq2))
            return lcs_len / max_len if max_len > 0 else 1.0
        
        def get_diff(self, seq1, seq2):
            """Get diff operations between sequences"""
            # Implementation would return edit operations
            pass

# Usage example
comparator = SequenceComparator(optimization_level=2)
similarity = comparator.similarity_score("ABCDE", "ACDFE")
print(f"Similarity: {similarity:.1%}")

def lcs_best_practices():
    """
    Best practices for LCS implementations
    """
    
    practices = {
        "Input Validation": [
            "Handle empty strings gracefully",
            "Validate input types (strings, lists, etc.)",
            "Consider case sensitivity requirements",
            "Check for very large inputs that might cause memory issues"
        ],
        
        "Algorithm Choice": [
            "Use space optimization for large sequences",
            "Consider memoization vs tabulation based on access patterns",
            "Implement early termination for obvious cases",
            "Choose appropriate data structures for the problem domain"
        ],
        
        "Performance": [
            "Profile memory usage for large problems",
            "Consider parallel computation for very large sequences",
            "Cache results for repeated queries",
            "Use appropriate string/sequence representations"
        ],
        
        "Maintainability": [
            "Separate LCS computation from path reconstruction",
            "Write comprehensive unit tests",
            "Document time and space complexity clearly",
            "Provide examples and use cases in documentation"
        ]
    }
    
    for category, tips in practices.items():
        print(f"\n{category}:")
        for tip in tips:
            print(f"  • {tip}")

lcs_best_practices()