java - Wagner Fischer算法在Java中的实现

我正试图使用wikipedia引用在java中实现Wagner-Fischer algorithm。
wagner-fischer
Java代码：

public class StringDistance {

public static void main(String[] args) {
    int i, j, m, n, temp, tracker;

    int[][] d = new int[50][50];

    String s = "kitten";
    String t = "sitting";

    char u[] = s.toCharArray();
    char v[] = t.toCharArray();

    m = u.length;
    n = v.length;

    for (i = 0; i <= m; i++) {
        d[i][0] = i;
    }
    for (j = 0; j <= n; j++) {
        d[0][j] = j;
    }

    for (j = 1; j <= m; j++) {
        for (i = 1; i <= n; i++) {
            if (u[i - 1] == v[j - 1]) {
                tracker = 0;
            } else {
                tracker = 1;
            }

            temp = Math.min((d[i - 1][j] + 1), (d[i][j - 1] + 1));
            d[i][j] = Math.min(temp, (d[i - 1][j - 1] + tracker));

        }
    }

    System.out.println("The levenstien distance" + d[n][m]);
}
}

但上面的代码只适用于长度相等的字符串。如果我想使这项工作不平等的字符串。请让我知道如何克服这个问题。
我正在获取索引越界错误：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
at StringDistance.main(StringDistance.java:32)

最佳答案

让我们去掉一些局部变量，以更清楚地说明发生这种情况的原因：

for (j = 1; j <= u.length; j++) {
    for (i = 1; i <= v.length; i++) {
        if (u[i - 1] == v[j - 1]) {
            tracker = 0;
        } else {
            tracker = 1;
        }

您使用i - 1（保证在v的范围内）作为u的索引，使用j - 1（保证在u的范围内）作为v的索引。
所以我怀疑这个表达：

u[i - 1] == v[j - 1]

应该只是

u[j - 1] == v[i - 1]

我还强烈建议只在第一次使用时，在最小范围内声明变量，使用基于0的索引，而不是基于1-Basic。条件运算符也有帮助。所以你的循环会变成：

for (int j = 0; j < u.length; j++) {
    for (int i = 0; i < v.length; i++) {
        int tracker = u[j] == v[i] ? 0 : 1;
        int temp = Math.min(d[i][j + 1] + 1, d[i + 1][j] + 1);
        d[i + 1][j + 1] = Math.min(temp, d[i][j] + tracker);
    }
}