java - 空間が最適化された最小共通部分列 (マルコフなので 2 列)

Question

ボトムアップの動的プログラミングを使用して、2 つの String オブジェクトの LCS を記述しようとしています。スペースで適切に機能させることができますO(mn)。ただし、ご覧のとおり、前の列がすべて必要なわけではありません。そこで、スペースが になるように 2 列に収まるように変更しようとしましたO(m)。ただし、すべての入力に対して機能するわけではありません (たとえば、 this:abcabcおよびabcbcca)。ここで何が欠けていますか？ハードウェアではなく、コンテストでもありません。DPの練習。

public int longestCommonSubsequence(String input) {
    char[] firstStr = this.string.toCharArray();
    char[] secondStr = input.toCharArray();
    int[][] maxLength = new int[firstStr.length+1][2];

    for(int i=0; i <= firstStr.length; i++) {
      maxLength[i][0] = 0;
    }
    for(int j=0; j < 2; j++) {
      maxLength[0][j] = 0;
    }

    for(int i=0; i < firstStr.length; i++) {
      for(int j=0; j < secondStr.length; j++) {
        if(firstStr[i] == secondStr[j]) {
          maxLength[i+1][1] = 1 + maxLength[i][0];
        }
        else {
          maxLength[i+1][1] = maxLength[i][1]>maxLength[i+1][0]?maxLength[i][1]:maxLength[i+1][0];
        }
      }
      //Copy second row to first row
      for(int l =0; l < firstStr.length; l++) {
        maxLength[l][0] = maxLength[l][1];
      }
    }

    return maxLength[firstStr.length -1][0];
  }

Answer 1

これには 2 つの問題があります。

    if(firstStr[i] == secondStr[j]) {
        maxLength[i+1][1] = 1 + maxLength[i][0];
        // check here if maxLength[i+1][1] is greather than the last max length
    }
    else {
        maxLength[i+1][1] = maxLength[i][1]>maxLength[i+1][0]?maxLength[i][1]:maxLength[i+1][0];
         // absolutely wrong: maxLength[i+1][1] = 0;
    }

ここでは、マイクロ最適化を使用したアルゴリズムを確認できます。

public static int lcs(String s0, String s1) {
    int maxLength = 0;
    int [][]lengths = new int[2][s1.length()+1];

    for (int i = 0; i < s0.length(); i++) {
        for (int j = 0; j < s1.length(); j++) {
            if (s0.charAt(i) == s1.charAt(j)) {
                lengths[0][j+1] = lengths[1][j] + 1;
                if (lengths[0][j+1] > maxLength) {
                    maxLength = lengths[0][j+1];
                }
            } else {
                lengths[0][j+1] = 0;
            }
        }
        int []temp = lengths[0];
        lengths[0] = lengths[1];
        lengths[1] = temp;
    }
    return maxLength; 
}