How many lines changed

diffing version control shortest path greedy

A version control system keeps the history of a file and for each commit shows how many lines were deleted and how many inserted. Its author wants to know the smallest possible number: how many lines at least must be deleted from the old version and inserted into it to obtain the new one. A whole line can only be deleted or inserted; a corrected line is one deletion and one insertion.

The example in the first test has three edits: the line «Еще ты дремлешь…» was deleted, the line «Ещё ты дремлешь…» (the same line of Pushkin, with ё) was inserted, and an empty line was added at the end. Files go up to a hundred thousand lines, but in the tests there are few differences, at most five hundred. The tests include real edits from the history of this site.

Input

The first line holds the numbers N and M (0 ≤ N, M ≤ 100,000): how many lines the old and the new version have. Then the N lines of the old version and the M lines of the new, in order. Lines may be empty and contain any characters except a line break; two lines are equal if they match character for character. The answer is at most 500.

Output

One number: the smallest total number of deleted and inserted lines.

Examples

Example 1

Input

3 4
Мороз и солнце; день чудесный!
Еще ты дремлешь, друг прелестный —
Пора, красавица, проснись:
Мороз и солнце; день чудесный!
Ещё ты дремлешь, друг прелестный —
Пора, красавица, проснись:

Output

Example 2

Input

7 6
A
B
C
A
B
B
A
C
B
A
B
A
C

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 11 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

If lines cannot be changed, only deleted and inserted, the answer is related to the longest common subsequence of lines: whatever is not in it is deleted from one version or inserted from the other. But an N × M table is ten billion cells.

2Hint 2

The answer is at most 500, so the path in the edit graph goes almost all the time along the diagonal. Search not by cells but by the number of edits: first everything reachable for free, then with one edit, with two…

3Hint 3

All paths with d edits end on diagonals k = x − y from −d to d. On each it is enough to remember the farthest point.

4The idea

Myers’ algorithm: for d = 0, 1, 2, … and each diagonal k from −d to d in steps of two, take the farthest point, a step down from diagonal k + 1 or right from k − 1, and go along the diagonal while the lines match. The first d at which the point reached (N, M) is the answer. The diff itself need not be recovered, so one array of 2(N + M) + 3 numbers is enough.

5Walkthrough

First replace lines with numbers: identical lines get identical numbers. Comparing numbers is cheaper than comparing strings, and lines in the tests can be long, like the HTML paragraphs of the course chapter in the fifth test. Then the loop from the article on Myers’ diff, only without saving the waves.

The answers on real edits match what git shows: 86 lines in the widget of the course on the fourth dimension, 56 in the plan of the mathematics textbook, 6 in the chapter on hashing, 18 in the loading of exchange rates.

5+Solution

6Complexity

O((N + M) · D) in the worst case and about N + M + D² on the tests of this problem: with D ≤ 500 there are about a hundred and twenty-five thousand evaluations on diagonals, plus the snakes. The table is O(N · M) for any answer: on the seventh test that is ten billion cells.

7Common mistakes

The edit distance table. Correct, but quadratic; memory for two rows of the table is enough, but time is not.
Substitution for one. By the statement a corrected line is a deletion and an insertion, that is, two edits. Levenshtein distance over lines gives less.
Splitting on spaces. Lines may be empty and contain spaces: input().split() will glue them together and lose them. Read by line breaks.
Empty versions. N or M can be zero; then the answer is the length of the other version, and the loop must survive it.

Algorithms behind it

STR Algorithm Myers’ diff The shortest script of line deletions and insertions in O((N + M) · D): waves by the number of edits. This is how git diff works. O((N + M) · D) 1 problem STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems DP Algorithm Longest common subsequence The longest chain common to two sequences: an m × n table, a path back, Hirschberg. O(m · n) 2 problems