diff

元の論文を読まずに、CやらRubyのソース辺をかき集めて動くように。

http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
http://raa.ruby-lang.org/search.rhtml?search=diff.rb

struct Diff_Result {
	int[][2] path;
}

Diff_Result diff(char[] data_a, char[] data_b)
{
	char[] A;
	char[] B;
	int[int] editgraph;
	
	Diff_Result create_path()
	{
		Diff_Result result;
		const int[1] zero = [0];
		int x = A.length; 
		int y = B.length;
		result.path[0] = (&x)[0..1].dup; 
		result.path[1] = (&y)[0..1].dup; 
		while(0 < x && 0 < y){
			int s = editgraph[x + y * B.length];
			if(s != 0){
				x -= s; 
				y -= s;
				result.path[0] ~= (&x)[0..1];
				result.path[1] ~= (&y)[0..1];
			}
			if((x + (y - 1) * B.length) in editgraph){
				do{
					--y;
				}while(0 < y && (x + (y - 1) * B.length) in editgraph);
				result.path[0] ~= (&x)[0..1]; 
				result.path[1] ~= (&y)[0..1]; 
			}
			if(((x - 1) + y * B.length) in editgraph){
				do{
					--x;
				}while(0 < x && ((x - 1) + y * B.length) in editgraph);
				result.path[0] ~= (&x)[0..1];
				result.path[1] ~= (&y)[0..1];
			}
		}
		if(result.path[0][result.path[0].length - 1] != 0 ||
			result.path[1][result.path[1].length - 1] != 0)
		{
			result.path[0] ~= zero;
			result.path[1] ~= zero;
		}
		result.path[0] = result.path[0].reverse;
		result.path[1] = result.path[1].reverse;
		return result;
	}
	
	int snake(int k, int fpa, int fpb)
	{
		int y = (fpa > fpb) ? fpa : fpb;
		int x = y - k;
		int M = A.length;
		int N = B.length;
		int count = 0;
		//printf("%d, %d"\n, x, y);
		while(x < M && y < N && A[x] == B[y]){
			++x;
			++y;
			++count;
		}
		editgraph[x + y * B.length] = count;
		return y;
	}

	if(data_a.length <= data_b.length){
		A = data_a;
		B = data_b;
	}else{
		A = data_b;
		B = data_a;
	}
	
	int M = A.length;
	int N = B.length;
	int[] fp;
	fp.length = M + N + 3;
	fp[0..fp.length] = -1;
	int offset = M + 1;
	int DELTA = N - M;
	assert(DELTA >= 0);
	for(int p = 0; p <= M; ++p){
		for(int k = -p; k < DELTA; ++k)
			fp[k + offset] = snake(k, fp[k-1+offset] + 1, fp[k+1+offset]);
		for(int k = DELTA + p; k >= DELTA; --k)
			fp[k + offset] = snake(k, fp[k-1+offset] + 1, fp[k+1+offset]);
		//printf("%d %d\n", fp[DELTA + offset], N);
		if(fp[DELTA + offset] == N)
		{
			Diff_Result result = create_path();
			if(data_a.length > data_b.length){
				int[] t = result.path[0];
				result.path[0] = result.path[1];
				result.path[1] = t;
			}
			return result;
		}
	}
	assert(false);
}

int main()
{
	char[] A = "ABCDEF";
	char[] B = "AB---CDEF";
	
	Diff_Result r = diff(A, B);
	for(int i = 0; i < r.path[0].length; ++i){
		printf("%d ", r.path[0][i]);
	}
	printf("\n");
	for(int i = 0; i < r.path[1].length; ++i){
		printf("%d ", r.path[1][i]);
	}
	
	return 0;
}

0 2 2 6
0 2 5 9

Thebeにバイナリ比較コマンドを実装するのに使おう。
それと、今さらながらに、静的配列って返せないんですね…。無駄にstructでラップが必要に…。