タスク定義:
私は独自の差分ユーティリティを作成しようとしています。インライン検索を実装したい。
2 つの段落のテキストがあることを意味します。制約された文字列の一般的な単語の合計が最大になるように、最初の段落 ( p1 ) から 2 番目の段落 ( p2 ) の文字列に文字列を定数化する必要があります。
そして、1 つの重要な点として、文字列を置き換えることはできません。つまり、p1[i] を p2[j] に定数化すると、k < i および v < の場合に p1[k] を p2[v] に定数化できません。 j.
ちょっとした例:
入力：
次の 2 つの段落があります。
"Very very very very" "Very very very"
"bla bla bla" "Very very very very very"
"looks like a very dump text" "One more sentence"
"simple text" "looks like a peace of ..."
"quite simple"
"bla bla bla bla"
...および行列ここで、matrix[i][j] = 文字列 p1[i] および p2[j] 内の一般的な単語の数
3 4 0 0 0 0
0 0 0 0 0 3
0 0 0 3 0 0
0 0 0 0 1 0
出力：
次の方法でそれらを定数化する必要があります。
---------------- "Very very very"
"Very very very very" "Very very very very very"
"bla bla bla" ----------------
---------------- "One more sentence"
"looks like a very dump text" "looks like a peace of ..."
"simple text" "quite simple"
---------------- "bla bla bla bla"
または、次の行列を形成することもできます。
(定数を持つ文字列のインデックス)
p1Indexes: [0, 2, 3]
p2Indexes: [1, 3 ,4]
質問：
このタスクの効率的なアルゴリズムは何ですか?
[必読ではありません] 直面した困難:
- インデックスコレクションを次の反復に渡す方法: 各反復ですべてのインデックスをコピーする必要があることを意味します
- 動的計画法を使用する場合は、共通の wors 数だけでなく、可能な反復ごとに 2 つのインデックス コレクションも格納する必要があります。
解決：
public void genConditionLCS() {
int i = -1;
int j = -1;
while (true) {
int[] indexes = nextIndexes(i+1, j+1);
i = indexes[0];
j = indexes[1];
if (i == -1 || j == -1) break;
firstParagraphIndexes.add(i);
secondParagraphIndexes.add(j);
}
}
private int[] nextIndexes(int i, int j) {
if ((i > (lcs.length-1)) || (j > (lcs[0].length-1)))
return new int[] {-1, -1};
int a = maxBenefit(i + 1, j);
int b = maxBenefit(i, j + 1);
int c = maxBenefit(i + 1, j + 1) + lcs[i][j];
if ((a == 0) && (b == 0) && (c == 0))
return new int[]{-1, -1};
else if (a >= b && a >= c)
return nextIndexes(i+1, j);
else if (b >= a && b >= c)
return nextIndexes(i, j+1);
else //if (c >= a && c >= b)
return new int[]{i, j};
}
private int maxBenefit(int i, int j) {
if ((i > lcs.length - 1) || (j > lcs[0].length - 1)) return 0;
int res = maxBenefit[i][j];
if (res == -1) {
int a = maxBenefit(i + 1, j);
int b = maxBenefit(i, j + 1);
int c = maxBenefit(i + 1, j + 1) + lcs[i][j];
res = max(a, b, c);
maxBenefit[i][j] = res;
}
return res;
}