Myers Diff Algorithm¶

def myers_diff(a, b):
    """
    Compute the difference between two sequences using Myers diff algorithm

    Args:
        a: First sequence
        b: Second sequence

    Returns:
        List of edit operations where:
        - ('+', i, x) means insert element x at position i
        - ('-', i, x) means delete element x at position i
    """
    # Create edit graph
    n = len(a)
    m = len(b)
    max_edit = n + m

    # Store furthest x coordinate on each k-line
    v = {1: 0}
    # Store path
    trace = []

    # Compute shortest edit path
    for d in range(max_edit + 1):
        # Save current d's path info
        trace.append(v.copy())

        for k in range(-d, d + 1, 2):
            # Determine whether to move down or right
            if k == -d or (k != d and v.get(k - 1, -1) < v.get(k + 1, -1)):
                x = v.get(k + 1, -1)  # Move down
            else:
                x = v.get(k - 1, -1) + 1  # Move right

            # Calculate y coordinate
            y = x - k

            # Move diagonally (matches)
            while x < n and y < m and a[x] == b[y]:
                x += 1
                y += 1

            # Update v
            v[k] = x

            # If reached endpoint, backtrack and return edit script
            if x >= n and y >= m:
                return _backtrack(a, b, trace, n, m)

    # If no path found (shouldn't happen)
    return []

def _backtrack(a, b, trace, x, y):
    """Backtrack to construct edit script"""
    result = []
    d = len(trace) - 1

    while d > 0:
        v = trace[d]
        k = x - y

        # Determine previous k value
        if k == -d or (k != d and v.get(k - 1, -1) < v.get(k + 1, -1)):
            prev_k = k + 1
        else:
            prev_k = k - 1

        # Calculate previous position
        prev_x = v.get(prev_k, 0)
        prev_y = prev_x - prev_k

        # Handle diagonal moves (matches)
        while x > prev_x and y > prev_y:
            x -= 1
            y -= 1

        # Record edit operation
        if x == prev_x:
            # Insert operation
            result.insert(0, ('+', x, b[prev_y]))
        else:
            # Delete operation
            result.insert(0, ('-', prev_x, a[prev_x]))

        # Update position
        x = prev_x
        y = prev_y
        d -= 1

    return result

# Test
a = "ABCABBA"
b = "CBABAC"
diff = myers_diff(a, b)
print("Diff result:", diff)

import java.util.*;

public class MyersDiff {
    public static void main(String[] args) {
        String a = "ABCABBA";
        String b = "CBABAC";
        List<EditOperation> diff = myersDiff(a, b);
        System.out.println("Diff result:");
        for (EditOperation op : diff) {
            System.out.println(op);
        }
    }

    // Edit operation class
    static class EditOperation {
        char type; // '+' for insert, '-' for delete
        int position;
        char element;

        public EditOperation(char type, int position, char element) {
            this.type = type;
            this.position = position;
            this.element = element;
        }

        @Override
        public String toString() {
            return "(" + type + ", " + position + ", " + element + ")";
        }
    }

    public static List<EditOperation> myersDiff(String a, String b) {
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        int n = aChars.length;
        int m = bChars.length;
        int maxEdit = n + m;

        // Store furthest x coordinate on each k-line
        Map<Integer, Integer> v = new HashMap<>();
        v.put(1, 0);

        // Store path
        List<Map<Integer, Integer>> trace = new ArrayList<>();

        // Compute shortest edit path
        for (int d = 0; d <= maxEdit; d++) {
            // Save current d's path info
            trace.add(new HashMap<>(v));

            for (int k = -d; k <= d; k += 2) {
                // Determine whether to move down or right
                int x;
                if (k == -d || (k != d && v.getOrDefault(k - 1, -1) < v.getOrDefault(k + 1, -1))) {
                    x = v.getOrDefault(k + 1, -1);  // Move down
                } else {
                    x = v.getOrDefault(k - 1, -1) + 1;  // Move right
                }

                // Calculate y coordinate
                int y = x - k;

                // Move diagonally (matches)
                while (x < n && y < m && aChars[x] == bChars[y]) {
                    x++;
                    y++;
                }

                // Update v
                v.put(k, x);

                // If reached endpoint, backtrack and return edit script
                if (x >= n && y >= m) {
                    return backtrack(aChars, bChars, trace, n, m);
                }
            }
        }

        // If no path found (shouldn't happen)
        return new ArrayList<>();
    }

    private static List<EditOperation> backtrack(char[] a, char[] b, List<Map<Integer, Integer>> trace, int x, int y) {
        List<EditOperation> result = new ArrayList<>();
        int d = trace.size() - 1;

        while (d > 0) {
            Map<Integer, Integer> v = trace.get(d);
            int k = x - y;

            // Determine previous k value
            int prevK;
            if (k == -d || (k != d && v.getOrDefault(k - 1, -1) < v.getOrDefault(k + 1, -1))) {
                prevK = k + 1;
            } else {
                prevK = k - 1;
            }

            // Calculate previous position
            int prevX = v.getOrDefault(prevK, 0);
            int prevY = prevX - prevK;

            // Handle diagonal moves (matches)
            while (x > prevX && y > prevY) {
                x--;
                y--;
            }

            // Record edit operation
            if (x == prevX) {
                // Insert operation
                result.add(0, new EditOperation('+', x, b[prevY]));
            } else {
                // Delete operation
                result.add(0, new EditOperation('-', prevX, a[prevX]));
            }

            // Update position
            x = prevX;
            y = prevY;
            d--;
        }

        return result;
    }
}