本文共 2185 字，大约阅读时间需要 7 分钟。
Java中查找两个字符串的最长公共子串
在编程过程中，经常会遇到需要比较两个字符串并找出它们的最长公共子串（LCS）的问题。虽然有多种算法可以实现这一功能，但其中一种比较直接且易于实现的方法是使用动态规划。这种算法通过记录每个位置的最大长度来逐步构建答案。
动态规划算法基本思路
动态规划算法通过创建一个二维数组来记录每个位置上可以形成的最长公共子串长度。具体来说，数组的每个元素代表在特定位置上两个字符串的共同子串的长度。
初始化：创建一个二维数组 record，其大小为 str1.length() x str2.length()。初始化时，所有元素的值由0或1组成，具体取决于当前字符是否相同。
填充记录数组：使用双重循环遍历两个字符串的每个字符。如果当前字符相同，则记录为当前位置和上一个位置的公共子串长度加一。如果不同，则记录为零。
跟踪最大长度：在遍历过程中，持续跟踪最长的公共子串长度和其结束位置。
构建结果：根据记录数组确定最长子串的位置并提取相应的子串。
优化建议
空间复杂度：需要尽量减少内存占用。当字符串较短时，记录数组的使用没有问题。但对于非常长的字符串，可以考虑使用一维数组记录每一行的最大长度，以降低空间复杂度。
时间复杂度：算法的时间复杂度为 O(n*m)，适合处理中短的到长的字符串。当字符串很长时，可以考虑使用更高效的哈希算法来实现。
结果选择策略：如果有多个子串长度相同，选择结束位置较远的作为结果，这有助于匹配较长的子串。
特殊情况处理：确保在字符串为空或全为相同字符的情况下，算法能正确运行并返回正确结果。
实现代码
package test;import java.util.Vector;public class test { public static String getChildStr(String str1, String str2) { int[][] record = new int[str1.length() + 1][str2.length() + 1]; int maxLen = 0; int maxEnd = 0; for (int i = 1; i <= str1.length(); ++i) { for (int j = 1; j <= str2.length(); ++j) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { record[i][j] = record[i - 1][j - 1] + 1; } else { record[i][j] = 0; } if (record[i][j] > maxLen) { maxLen = record[i][j]; maxEnd = j; } } } return str1.substring(maxEnd - maxLen, maxEnd); } public static void main(String[] args) { long start = System.currentTimeMillis(); String result = getChildStr("ajhf;ajkdjan;kjdfck;fjdfnkjdasjfo;iaejfaeiojrdfoijoifdjvo;iaejroifjfvaoedrjvodifjv;ILOVEYOU", "ILOVEyou"); long end = System.currentTimeMillis(); System.out.println(result); System.out.println(end - start); }} 测试结果分析
在执行代码时，可以根据输出结果来验证算法的正确性。例如，输入两个相似但有差异的字符串，代码应该返回它们的最长公共子串。
字符串对齐和边界处理：在代码中使用 i == 0 || j == 0 来处理边界条件，防止IndexOutOfBoundsException。
记录数组维护：record 数组保留了每个位置的最大长度，确保在寻找结果时可以回到正确的位置构建子串。
优化空间复杂度：在代码中将记录数组的大小设置为 str1.length() + 1 和 str2.length() + 1，以便于在处理边界时避免数组越界。
总结
通过上述分析和优化，可以看到动态规划算法在查找两个字符串的最长公共子串方面表现稳定且可靠。对于大部分应用场景，这个方法既简单又有效。对于更复杂的需求，可以进一步结合哈希和滑动窗口技术来优化性能。
发表评论
最新留言
关于作者
