qq_37862886
我欲修仙法力无边
采纳率36.4%
2017-03-12 14:48

获取两个字符串中最大相同子串

获取两个字符串中最大相同子串
例如找到字符串"abcwerthelloyuiodef"和"cvhellobnm"中的最大相同字串

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • caozhy 从今以后生命中的每一秒都属于我爱的人 4年前
     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());
        }
    }
    
    点赞 2 评论 复制链接分享
  • caozhy 从今以后生命中的每一秒都属于我爱的人 4年前
    点赞 1 评论 复制链接分享

相关推荐