获取两个字符串中最大相同子串
例如找到字符串"abcwerthelloyuiodef"和"cvhellobnm"中的最大相同字串
获取两个字符串中最大相同子串
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- threenewbee 2017-03-12 15:06关注
public class LCString2 { public static void getLCString(char[] str1, char[] str2) { int i, j; int len1, len2; len1 = str1.length; len2 = str2.length; int maxLen = len1 > len2 ? len1 : len2; int[] max = new int[maxLen]; int[] maxIndex = new int[maxLen]; int[] c = new int[maxLen]; // 记录对角线上的相等值的个数 for (i = 0; i < len2; i++) { for (j = len1 - 1; j >= 0; j--) { if (str2[i] == str1[j]) { if ((i == 0) || (j == 0)) c[j] = 1; else c[j] = c[j - 1] + 1; } else { c[j] = 0; } if (c[j] > max[0]) { // 如果是大于那暂时只有一个是最长的,而且要把后面的清0; max[0] = c[j]; // 记录对角线元素的最大值,之后在遍历时用作提取子串的长度 maxIndex[0] = j; // 记录对角线元素最大值的位置 for (int k = 1; k < maxLen; k++) { max[k] = 0; maxIndex[k] = 0; } } else if (c[j] == max[0]) { // 有多个是相同长度的子串 for (int k = 1; k < maxLen; k++) { if (max[k] == 0) { max[k] = c[j]; maxIndex[k] = j; break; // 在后面加一个就要退出循环了 } } } } } for (j = 0; j < maxLen; j++) { if (max[j] > 0) { System.out.println("第" + (j + 1) + "个公共子串:"); for (i = maxIndex[j] - max[j] + 1; i <= maxIndex[j]; i++) System.out.print(str1[i]); System.out.println(" "); } } } public static void main(String[] args) { String str1 = new String("abcwerthelloyuiodef"); String str2 = new String("cvhellobnm"); getLCString(str1.toCharArray(), str2.toCharArray()); } }
解决 无用评论 打赏 举报
悬赏问题
- ¥20 ML307A在使用AT命令连接EMQX平台的MQTT时被拒绝
- ¥20 腾讯企业邮箱邮件可以恢复么
- ¥15 有人知道怎么将自己的迁移策略布到edgecloudsim上使用吗?
- ¥15 错误 LNK2001 无法解析的外部符号
- ¥50 安装pyaudiokits失败
- ¥15 计组这些题应该咋做呀
- ¥60 更换迈创SOL6M4AE卡的时候,驱动要重新装才能使用,怎么解决?
- ¥15 让node服务器有自动加载文件的功能
- ¥15 jmeter脚本回放有的是对的有的是错的
- ¥15 r语言蛋白组学相关问题