Git: A line diff from the longest common subsequence

Compute a diff the way version control does.

What to build

A program that prints a line-by-line diff of two versions of a file.

Requirements

  • Keep a longest common subsequence of lines, using exactly the table and walk in the hints so the output is the same for everyone.
  • Print each line of the diff: line for a kept line, -line for a removed line, +line for an added line.

Input

Line 1: n, then the n old lines. Then m, then the m new lines.

Output

One line per diff line.

Constraints

n, m ≤ 300.

Example

Input:

3
a
b
c
3
a
x
c

Output:

 a
-b
+x
 c

Why it works

The longest common subsequence is the most that can stay unchanged, so reporting everything else as removed or added describes the change with the fewest edits.

Examples

Example 1 · Input
3
a
b
c
3
a
x
c
Expected output
 a
-b
+x
 c
Example 2 · Input
2
one
two
3
one
two
three
Expected output
 one
 two
+three

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Fill L[i][j] from the end: L[i][j] = L[i+1][j+1] + 1 when the lines are equal, else max(L[i+1][j], L[i][j+1]).

Hint 2

Walk from (0, 0): equal lines are kept; otherwise remove old[i] if j is at the end or L[i+1][j] ≥ L[i][j+1], else add new[j].

Solution

Show one correct solution (try it yourself first)
old = [input() for _ in range(int(input()))]
new = [input() for _ in range(int(input()))]
n, m = len(old), len(new)
L = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
    for j in range(m - 1, -1, -1):
        L[i][j] = L[i + 1][j + 1] + 1 if old[i] == new[j] else max(L[i + 1][j], L[i][j + 1])
i = j = 0
while i < n or j < m:
    if i < n and j < m and old[i] == new[j]:
        print(" " + old[i])
        i, j = i + 1, j + 1
    elif j == m or (i < n and L[i + 1][j] >= L[i][j + 1]):
        print("-" + old[i])
        i += 1
    else:
        print("+" + new[j])
        j += 1

Lesson: Viewing changes: diff, log and blame →