package jp.ac.osaka_u.ist.sel.t_kanda.tkdiff;

import java.util.ArrayList;
import java.util.List;
import java.util.RandomAccess;

public class SED {
	private int[] fp;
	private int offset;
	private List<?> a, b;

	public <E> int diff(List<E> listA, List<E> listB) {
		if (listA.size() > listB.size()) {
			List<E> t = listA;
			listA = listB;
			listB = t;
		}
		if (listA instanceof RandomAccess) {
			a = listA;
		} else {
			a = new ArrayList<>(listA);
		}
		if (listB instanceof RandomAccess) {
			b = listB;
		} else {
			b = new ArrayList<>(listB);
		}
		int delta = b.size() - a.size();
		offset = a.size();
		fp = new int[a.size() + b.size() + 1];
		for (int i = 0; i < fp.length; i++) {
			fp[i] = Integer.MIN_VALUE;
		}
		fp[offset] = 0;
		snake(0);
		for (int i = 1; i <= delta; i++) {
			line(i);
		}
		int p = 0;
		while (fp[delta + offset] != b.size()) {
			p++;
			for (int i = -p; i < delta; i++) {
				line(i);
			}
			for (int i = delta + p; i > delta; i--) {
				line(i);
			}
			line(delta);
		}
		int sed = p * 2 + delta;
		return sed;
	}

	private void snake(int i) {
		int x = -i + fp[i + offset];
		int y = fp[i + offset];
		while (x < a.size() && y < b.size() && a.get(x).equals(b.get(y))) {
			fp[i + offset]++;
			x++;
			y++;
		}
	}

	private void line(int i) {
		fp[i + offset] = Math.max(fp[i - 1 + offset] + 1, fp[i + 1 + offset]);
		snake(i);
	}
}
