文字列探索プログラムの日本語化について

[せうご]

コード:

#include <stdio.h>
#include <string.h>
char S1[100], S2[100];
//最少値を求める
int min(int a, int b, int c)
{
	return a > b ? (b > c ? c : b) : (a > c ? c : a);
}
int main()
{
	scanf("%s", S1);
	scanf("%s", S2);
	//編集距離計算
	int lenstr1 = strlen(S1) + 1;
	int lenstr2 = strlen(S2) + 1;
	int d[100][100];
	int i1 = 0, i2 = 0, cost = 0;

	for (; i1 < lenstr1; i1++) d[i1][0] = i1;
	for (; i2 < lenstr2; i2++) d[0][i2] = i2;

	for (i1 = 1; i1 < lenstr1; i1++) {
		for (i2 = 1; i2 < lenstr2; i2++) {
			cost = S1[i1 - 1] == S2[i2 - 1] ? 0 : 1;
			d[i1][i2] = min(d[i1 - 1][i2] + 1, d[i1][i2 - 1] + 1, d[i1 - 1][i2 - 1] + cost);
		}
	}

	printf("編集距離は%dです\n", d[lenstr1 - 1][lenstr2 - 1]);
}

このプログラムを日本語対応しようとしているのですが、正確な値が出せません。
例えば、あいうえお、いうえお、という文字列を比較した際、編集距離は1になるはずなのですが
２と表示されてしまいます。
ご教授お願い致します。

[かずま]

wchar_t と locale を使えばよいでしょう、

コード:

#include <stdio.h>
#include <wchar.h>   // wcslen     // 変更
#include <locale.h>  // setlocale  // 追加

wchar_t S1[100], S2[100];          // 変更

int min(int a, int b, int c)
{
    return a > b ? (b > c ? c : b) : (a > c ? c : a);
}

int main()
{
    setlocale(LC_CTYPE, "");       // 追加
    scanf("%ls", S1);              // 変更
    scanf("%ls", S2);              // 変更
    //編集距離計算
    int lenstr1 = wcslen(S1) + 1;
    int lenstr2 = wcslen(S2) + 1;
    int d[100][100];
    int i1 = 0, i2 = 0, cost = 0;
 
    for (; i1 < lenstr1; i1++) d[i1][0] = i1;
    for (; i2 < lenstr2; i2++) d[0][i2] = i2;
 
    for (i1 = 1; i1 < lenstr1; i1++) {
        for (i2 = 1; i2 < lenstr2; i2++) {
            cost = S1[i1 - 1] == S2[i2 - 1] ? 0 : 1;
            d[i1][i2] = min(d[i1 - 1][i2] + 1, d[i1][i2 - 1] + 1, d[i1 - 1][i2 - 1] + cost);
        }
    }
 
    printf("編集距離は%dです\n", d[lenstr1 - 1][lenstr2 - 1]);
}

[せうご]

ありがとうございます。
ご指摘のようにwchar_tを使った方法は検討したのですが、エラーこそ起きないものの、正しい結果が表示されませんでした。
例えばきりぎりすときらぎすを比べた際、結果は2となるはずが1となってしまいます。
計算方法そのものに間違いがあるのでしょうか。
ご検討お願いします。

[かずま]

OS とコンパイラは何ですか？

Linux の gcc では、問題なく編集距離は 2 になりました。

Windows の VC++ の scanf の "%ls" には、バグがあるようです。
次のように wscanf を使用すると、このバグを回避できるようです。

コード:

    wscanf(L"%ls", S1);
    wscanf(L"%ls", S2);

[かずま]

まだ解決にならないのでしょうか？

int d[100][100]; ですが、表を上から順番に作っていくので、
ある行と、その次の行の二つの行だけでできます。

コード:

#include <stdio.h>   // printf
#include <wchar.h>   // wcslen, wscanf
#include <locale.h>  // setlocale
 
int min(int a, int b, int c)
{
    return a < b ? (a < c ? a : c) : (b < c ? b : c);
}
 
int main(void)
{
    setlocale(LC_CTYPE, "");

    wchar_t s1[100], s2[100];
    wscanf(L"%ls", s1), wscanf(L"%ls", s2);
    int n1 = wcslen(s1), n2 = wcslen(s2);
    int d[2][100], *a = d[0], *b = d[1], *t;
 
    for (int j = 0; j <= n2; j++) a[j] = j;

    for (int i = 0; i < n1; i++) {
        b[0] = i + 1;
        for (int j = 0; j < n2; j++)
            b[j+1] = min(a[j+1] + 1, b[j] + 1, a[j] + (s1[i] != s2[j]));
        t = a, a = b, b = t;
    }

    printf("編集距離は %d です\n", a[n2]);
}