任务定义：
我尝试编写自己的差异工具。我想实现内联搜索。
意味着我有两段文字。我必须将第一段（p1）中的字符串限制为第二段（p2）中的字符串，以使受限制字符串中的常用单词总和最大。
还有一点很重要，你不能替换字符串：我的意思是如果你将 p1[i] 限制为 p2[j]，那么你不能将 p1[k] 限制为 p2[v] 如果 k < i 和 v < j.
小例子：
输入：
你有两个段落：
"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 编号，还需要为每个可能的迭代存储两个索引集合。
解决方案：
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;
}