C言語でdiffコマンドを書きたい

■要求定義
– ファイルとファイルの内容の違いを表示する
– diff 旧ファイル名 新ファイル名

■diffのサンプル
e.g.
before.txt

体重 66Kg
abcdef
123456

after.txt

体重 64Kg
abcdef
123456

$ diff before.txt after.txt
1c1
< 体重 66Kg --- > 体重 64Kg

■検討
– 差分の計算には(1)編集距離、(2)Longest Common Subsequence:最長共通部分列、(3)Shortest Edit Script
– Wuアルゴリズムでは、2つの要素列を、エディットグラフに見立てて、点(0,0)から点(M,N)までの最短経路を求める問題に還元する
– Wuアルゴリズムは難易度が高いか？

同じか否かを検出

int main(){

	int i, n, c1, c2;
	FILE *fp1, *fp2;

	fp1 = fopen("before.txt", "r");
	fp2 = fopen("after.txt", "r");

	if(fp1==NULL || fp2==NULL){
		printf("file open error\n");
		return 1;
	}

	int ln = 1;
	int cl = 0;

	while ((c1=fgetc(fp1))!=EOF && (c2=fgetc(fp2))!=EOF){
		ln += (c1 == '\n') ? 1: 0;
		cl += (c1 == '\n') ? 0: ++cl;

		if(c1 != c2){
			printf("difference found [%c][%c] at line %d col %d\n", c1, c2, ln, cl);
			fclose(fp1);
			fclose(fp2);
			return 2;
		}

	}
	printf("no difference\n");

	fclose(fp1);
	fclose(fp2);

	return 0;
}

$ ./dev
difference found [6][4] at line 1 col 1022
$ ./dev
no difference
天才がいるな。

■動的計画法(JavaScript)

function distance(A, B){
	const M = A.length;
	const N = B.length;
	// DPのテーブル(大きさ(M + 1)*(N + 1)の2次元配列)
	// D[i][j] = (0, 0)から(i, j)までの最小コスト(編集距離)
	const D = new Array(M + 1);
	for(let i = 0; i <= M; i++){
		D[i] = new Array(N + 1);
		// (0,0)から(i,0)までの距離はi
		D[i][0] = i;
	}
	for(let j = 1; j <= N; j++){
		// (0,0)から(0, j)までの距離はj
		D[0][j] = j;
	}
	// D[i][j]を順番に求める
	for(let i = 1; i <= M; i++){
		for(let j = 1; j <= N; j++){
			// 縦横については +1, 斜めの辺については + 0
			D[i][j] = A[i-1] === B[j - 1]
			 ? Math.min(D[i-1][j] +1, D[i][j-1]+1, D[i-1][j-1])
			 : Math.min(D[i-1][j] +1, D[i][j-1]+1); 
		}
	}
	return D[M][N];
}

gonpなどwuアルゴリズムにはライブラリがあるようです。