test.py

from collections import defaultdict

def remove_longest_prefix(A, B, n):
    len_A, len_B = len(A), len(B)
    
    if n >= len_A:
        return B[len_A:] if len_A <= len_B else B
    
    max_match = 0
    best_pos = 0
    
    # 构建字符位置映射表（包含偏移量限制）
    char_index = defaultdict(list)
    max_offset = min(len_A + n, len_B)  # 添加偏移量限制
    for i, c in enumerate(B[:max_offset]):
        char_index[c].append(i)
    
    # 逆向扫描关键字符
    for a_pos in reversed(range(len_A)):
        target_char = A[a_pos]
        if target_char not in char_index:
            continue
            
        # 检查可能匹配的位置范围
        for b_start in char_index[target_char]:
            # 增加位置有效性验证
            if b_start < max(0, a_pos - n) or b_start > min(len_B, a_pos + n):
                continue
                
            # 计算动态窗口范围
            window_start = max(0, b_start - a_pos)
            window_size = min(a_pos + n + 1, len_A, len_B - window_start)
            
            # 初始化DP数组（修复索引问题）
            prev_row = list(range(window_start, window_start + window_size + 1))
            
            # 动态规划计算（添加边界保护）
            for i in range(1, window_size + 1):
                current_row = [prev_row[0] + 1]  # 第一个元素单独处理
                for j in range(1, window_size + 1):
                    # 添加索引有效性检查
                    if (window_start + j - 1) >= len_B:
                        break
                        
                    cost = 0 if A[i-1] == B[window_start + j -1] else 1
                    current_row.append(min(
                        prev_row[j-1] + cost,
                        prev_row[j] + 1 if j < len(prev_row) else float('inf'),
                        current_row[j-1] + 1
                    ))
                    # 提前终止条件
                    if current_row[-1] > n:
                        break
                prev_row = current_row
                if all(v > n for v in current_row):
                    break
                    
            # 更新最佳匹配（添加有效性验证）
            if window_size > 0 and prev_row[-1] <= n and (a_pos +1) > max_match:
                max_match = a_pos +1
                best_pos = window_start + window_size
                
    return B[best_pos:] if max_match >0 else B

A = "#include<assert.h>\n#include<bits/stdc++.h>\n// Check if in given vector of numbers, are any two numbers closer to each other than\n// given threshold.\n// >>> has_close_elements((std::vector<float>({(float)1.0f, (float)2.0f, (float)3.0f})), (0.5f))\n// (false)\n// >>> has_close_elements((std::vector<float>({(float)1.0f, (float)2.8f, (float)3.0f, (float)4.0f, (float)5.0f, (float)2.0f})), (0.3f))\n// (true)\nbool has_close_elements(std::vector<float> numbers, float threshold) {\n"
B = "#include <assert.h>\n#include <bits/stdc++.h>\n\n// Check if in given vector of numbers, are any two numbers closer to each other than\n// given threshold.\n// >>> has_close_elements((std::vector<float>({(float)1.0f, (float)2.0f, (float)3.0f})), (0.5f))\n// (false)\n// >>> has_close_elements((std::vector<float>({(float)1.0f, (float)2.8f, (float)3.0f, (float)4.0f, (float)5.0f, (float)2.0f})), (0.3f))\n// (true)\nbool has_close_elements(std::vector<float> numbers, float threshold) {\n    // Sort the vector in ascending order\n    std::sort(numbers.begin(), numbers.end());\n\n    // Iterate over the sorted vector\n    for (size_t i = 0; i < numbers.size() - 1; ++i) {\n        // Check if the difference between the current element and the next element is less than the threshold\n        if (numbers[i + 1] - numbers[i] < threshold) {\n            return true; // If a pair of elements is found that are closer than the threshold, return true\n        }\n    }\n\n    // If no pair of elements is found that are closer than the threshold, return false\n    return false;\n}\n\nint main() {\n    std::vector<float> numbers1 = {1.0f, 2.0f, 3.0f};\n    std::vector<float> numbers2 = {1.0f, 2.8f, 3.0f, 4.0f, 5.0f, 2.0f};\n\n    std::cout << std::boolalpha << has_close_elements(numbers1, 0.5f) << std::endl; // Output: false\n    std::cout << std::boolalpha << has_close_elements(numbers2, 0.3f) << std::endl; // Output: true\n\n    return 0;\n}\n"
n = 5
print(remove_longest_prefix(A, B, n))