Edit Script: + - =

The LCS tells you what SURVIVES. An edit script turns that into instructions: one line per item, saying whether it was kept, deleted from A, or inserted from B.

Reading a script

Take A = ABCBDAB and B = BDCAB, and keep the LCS BDAB:

-A     delete A's leading A
=B     keep
-C     delete
=B     keep
=D     keep
+C     insert B's C
=A     keep
=B     keep

Read the = and - lines top to bottom and you get ABCBDAB back. Read the = and + lines and you get BDCAB. That round-trip property is what makes a script a patch: it carries enough to rebuild either side.

The marker is =, not a space

Unified diff — the format later lessons build — writes a space for a kept line. This lesson's script writes a literal =. Same idea, different byte, and the exercise on this page compares bytes: a script that emits B where =B was asked for is wrong on every kept line at once. It is the single most common way to fail this exercise.

Generating it

Fill the LCS table, then walk it backwards from (n, m). A match steps diagonally; otherwise step toward the larger neighbour, and on a tie step left (insert) first. Because you walk backwards, reverse the result before printing.

Why the tie-break has to be written down

ABCBDAB and BDCAB have two different LCSs of length 4, so there are several scripts of the same minimal size and no way to call one of them 'the' answer. Any tool that has to agree with another tool — a grader, a patch applier, a regression test — must therefore fix a rule and state it. Ours is the one above: prefer the match, and on a tie prefer the insert.