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:
linefor a kept line,-linefor a removed line,+linefor 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