HDU|HDU 1503 Advanced Fruits 最长公共子串应用（LCS算法应用）
【HDU|HDU 1503 Advanced Fruits 最长公共子串应用（LCS算法应用）】LCS 算法应用，求出最长公共子串，而非长度。
文章图片
LCS 算法轨迹，来自算法导论
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
* 题意：把两个单词拼接成一个新单词，使得新单词的子序列中包含两个单词，并且要使这个新单词最短
*
* 思路：先利用 LCS 算法求出最长公共子串，然后拼接输出即可。
*
*/
public class Main {private static int[][] maxLen = new int[1000][1000];
private static String work(String str1, String str2) {
StringBuilder result = new StringBuilder();
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
int length1 = ch1.length;
int length2 = ch2.length;
// 正常 LCS 算法
for (int indexI = 1;
indexI <= length1;
indexI++) {
for (int indexJ = 1;
indexJ <= length2;
indexJ++) {
if (ch1[indexI - 1] == ch2[indexJ - 1]) {
maxLen[indexI][indexJ] = maxLen[indexI - 1][indexJ - 1] + 1;
} else {
maxLen[indexI][indexJ] = Math.max(maxLen[indexI - 1][indexJ], maxLen[indexI][indexJ - 1]);
}
}
}
// 规则处理：当没有最长公共子串时，输出两个字符串全部字符。
if (maxLen[length1][length2] == 0) {
result.append(str1).append(str2);
} else {
int indexI = length1;
int indexJ = length2;
// 反向进行比较
while (indexI > 0 && indexJ > 0) {
// 将最长公共子串字符拼接到 result
if (maxLen[indexI][indexJ] == maxLen[indexI - 1][indexJ - 1] + 1 && ch1[indexI - 1] == ch2[indexJ - 1]) {
result.append(ch1[indexI - 1]);
indexI--;
indexJ--;
} else {
// 将两个字符串中字符（不属于最长公共子串的字符）拼接到 result
if (maxLen[indexI][indexJ] == maxLen[indexI - 1][indexJ]) {
result.append(ch1[--indexI]);
} else {
result.append(ch2[--indexJ]);
}
}
}
// 将剩余的字符全部存储到 result
while (indexI > 0) {
result.append(ch1[--indexI]);
}
while (indexJ > 0) {
result.append(ch2[--indexJ]);
}
}
return result.reverse().toString();
}public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
String str1;
String str2;
while (in.hasNext()) {
str1 = in.next();
str2 = in.next();
out.println(work(str1, str2));
}
out.flush();
}
}
推荐阅读
- Vagrant|Vagrant (四) Advanced of Box
- 推动智能电网在5G-Advanced标准落地！展锐携手产业伙伴紧密行动
- HDU 5528【2015长春现场赛 B】 Count a * b
- hdu5289|hdu5289 Assignment（极差＜k的子区间数量，单调性证明+双指针+单调队列）
- hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)
- HDU-5628-Clarke-and-math-狄利克雷卷积
- HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
- 主席树|HDU4417（主席树）
- HDU 5184 Brackets (卡特兰数)
- HDU 5185 Equation (DP)