Spaces:
Sleeping
Sleeping
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)) |