「動的計画法」を用いdiffコマンドを実装

締切済

質問者：thlka
質問日時：2011/06/09 13:19
回答数：1件

こんにちは、
皆様のお知恵をお借りしたく投稿させていただきました。

「動的計画法」を用い(C言語)diffコマンドを実装したいというのが今回の質問の内容です。

二つのテキストa,bがあるとします。

[atxt]
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaab
aaaaaaaaaaaaaac
aaaaaaaaaaaaaad
11111
22222
33333
44444

[b.txt]
aaaaaaaaaaaaaaa
aaaaaaaaaaaaabb
aaaaaaaaaaaaacc
aaaaaaaaaaaaaad
eeeeeeeeeeeeeee
11111
44444

この二つのテキストを見比べると・・・

どちらも2行3行目が違う(2,3c2,3)
aは5行目にeee・・・がない(4a5)
bは22222,33333がない(6,7d6)

[出力結果]
2,3c2,3
<aaaaaaaaaaaaaab
<aaaaaaaaaaaaaac
---
>aaaaaaaaaaaaabb
>aaaaaaaaaaaaacc
4a5
>eeeeeeeeeeeeeee
7,8d5
<22222
<33333

↑というように出力されるようにdiffコマンドを実装したいです。

ーー＝Cプログラムーーー

#include <stdio.h>

struct text_info
{
char* content;
int length;
struct text_info* next;
};

int read_file( const char* filename, struct text_info** info )
{
FILE* fp;
struct text_info *current_info;
struct text_info *next_info;
ssize_t line_size;
char* buff = NULL;
size_t buf_size = 0;
int count = 0;

fp = fopen( filename, "ra" );
if( fp == NULL )
{
perror(filename);
exit(-1);
}
*info = (struct text_info*)malloc(sizeof(struct text_info));
current_info = *info;
current_info->content = NULL;
current_info->length = 0;
current_info->next = NULL;

while( (line_size = getline(&buff,&buf_size,fp)) != -1 )
{
current_info->content = (char*)malloc(sizeof(char)*(line_size+1));
strcpy(current_info->content,buff);
current_info->length = line_size;

next_info = (struct text_info*)malloc(sizeof(struct text_info));
next_info->content = NULL;
next_info->length = 0;
next_info->next = NULL;

current_info->next = next_info;
current_info = next_info;

count++;
}
if( buff )
free(buff);
fclose(fp);

return count;
}
void conv_text_info_to_string_array( const struct text_info* info,
int linenum,
char*** array )
{
int count = 0;

*array = (char**)malloc(sizeof(char*)*linenum);
while( count < linenum && info != NULL )
{
// printf("%d\n",count);
(*array)[linenum-count-1] = info->content;
info = info->next;
count++;
}
}

/* ↓以下の関数を完成させたい */

void dp( char** array_input, int in_linenum,
char** array_ref, int ref_linenum )
{
int i,j;

printf("*** 入力ファイル ***\n");
for( i = 0; i < in_linenum; i++ )
printf("%s",array_input[i]);
printf("*** 参照ファイル ***\n");
for( j = 0; j < ref_linenum; j++ )
printf("%s",array_ref[j]);
}

int main(int argc, char* argv[])
{
struct text_info *in_info, *ref_info;
int in_linenum, ref_linenum;
char **in_array, **ref_array;

if( argc < 3 )
{
printf("%s input.txt refer.txt\n",argv[0]);
return -1;
}

printf("read input file\n");
in_linenum = read_file( argv[1], &in_info );
printf("%d lines read.\n",in_linenum);
conv_text_info_to_string_array( in_info, in_linenum, &in_array );

printf("read reference file\n");
ref_linenum = read_file( argv[2], &ref_info );
printf("%d lines read.\n",ref_linenum);

conv_text_info_to_string_array( ref_info, ref_linenum, &ref_array );

dp( in_array, in_linenum, ref_array, ref_linenum );
}

ーーーーーーーーーーーーーーーーーーーーーーーーーー

dp関数をどうしていいか分からず悩んでいます。
皆様のお力をお貸しください。