assert reconstructed == new # round-trip guaranteed
The implementation provides a full Myers diff algorithm in Python with three main capabilities:
1. shortest_edit_script(a, b) — character-level Myers diff returning edit operations
2. unified_diff(a, b) — line-level unified diff output (standard format with @@ hunks)
3. apply_patch(original, patch) — reconstruct the new string by applying a unified diff patch
Core algorithm (Myers O(ND)):
def _myers(a: List[str], b: List[str]) -> List[Tuple[int, int, str]]:
n, m = len(a), len(b)
V = {1: 0}
traces: List[dict] = []
for d in range(n + m + 1):
for k in range(-d, d + 1, 2):
if k == -d or (k != d and V.get(k - 1, -10**9) < V.get(k + 1, -10**9)):
x = V.get(k + 1, 0) # came from k+1, move down
else:
x = V.get(k - 1, 0) + 1 # came from k-1, move right
y = x - k
while x < n and y < m and a[x] == b[y]:
x += 1; y += 1
V[k] = x
if x >= n and y >= m:
traces.append(V.copy())
return _backtrack(traces, d, n, m)
traces.append(V.copy())
return []
Usage example:
from myers_diff import unified_diff, apply_patch
old = "line1\nline2\nline3\nline4\nline5\n"
new = "line1\nmodified\nline3\nline4\nnewline\n"
# Produce unified diff
diff = unified_diff(old, new)
print(diff)
# --- a
# +++ b
# @@ -1,5 +1,5 @@
# line1
# -line2
# +modified
# line3
# line4
# -line5
# +newline
# Apply patch to reconstruct
reconstructed = apply_patch(old, diff)
assert reconstructed == new # round-trip guaranteed
Verified with 24 automated tests covering: | Category | Tests | |---|---| | **Character-level** | `abc→abd` (2 ops), empty→empty (0), empty→abc (3 inserts), abc→empty (3 deletes), identical strings (0 ops), completely different `abc→xyz` (6 ops) | | **Line-level diff** | Empty→empty (empty diff), identical lines (empty diff), single change produces correct `@@` hunk | | **Patch round-trip** | 9 round-trip tests including empty→empty, empty→new content, only original→empty, single change, multiple changes, non-adjacent changes | | **Char diff output** | Correct headers, shows deletions with `-`, insertions with `+` | | **Edge cases** | Long identical strings, trailing newline handling, empty patch | **Key results:** - All 24/24 tests passed - Patch round-trip is perfect: `apply_patch(original, unified_diff(original, modified)) == modified` for all tested cases - Handles empty strings, single-line, multi-line, and completely different inputs **Edge cases handled:** - Empty strings on either or both sides - Strings with no changes (empty diff, returns original from patch) - Trailing newlines preserved correctly - Multiple non-adjacent hunks - Single-character differences - Complete replacement (all characters/lines different) ---
{"model": "deepseek-v4-flash", "problem_class": "str-diff-patch-myers", "result": "passed", "tests": 24}