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

获取两个字符串中最长相同子串。比如： str1 = “abcwerthelloyuiodef “;str2 = “cvhellobnm” 提示：将短的那个串进行长度依次递减的子串与较长的串比较。 int length = str2.length(); // 用于控制子串的长度

方法一：暴力法
1.计算str2 的所有子串数（排列组合），保存在n中

int n = 0;

        for (int i = 0; i < str2.length(); i++) {

            n += i;

        }

2.创建一个字符数组保存str2的所有子串，用String的Substring切割得到子串，加一个count计数器

String[] s = new String[n];
        int count = 0;
        for (int k = 0; k < str2.length() - 1; k++) {
            for (int i = k; i < str2.length() - 1; i++) {

                s[count++] = str2.substring(k, i + 2);


            }

        }

3.创建新的数组s1来保存符合条件的子串，遍历s数组，indexOf(s[i])判断每一个子串是否有匹配项，将匹配的字符串存进s1中

String[] s1 = new String[count];

  
        int m = 0;
        for (int i = 0; i < count; i++) {


            if (str1.indexOf(s[i]) > 0) {

                s1[m++] = s[i];


            }


        }

4.此时s1中存放的都是两个字符串中的相同子串，找到字符串元素的最大长度，不能直接输出最长的子串，此时不确定长度最长的子串的个数，所以拿到最长长度就够了

int maxLength = 0;


        for (int j = 0; j < m; j++) {


            if (s1[j].length() > maxLength) {
                maxLength = s1[j].length();
            }


        }

5.遍历数组，长度等于最长长度的字符串全部输出，s1不是完美数组，所以要进行非空判断

for (String i : s1) {

            if (i != null) {

                if (i.length() == maxLength) {

                    System.out.println(i);

                }


            }


        }

全部代码

 @Test
    public void test4() {


        String str1 = "abcwerthelloyuhelloiodef ";
        String str2 = "cvhellobnm";
        int n = 0;

        for (int i = 0; i < str2.length(); i++) {

            n += i;

        }
        System.out.println(n);


        String[] s = new String[n];
        int count = 0;
        for (int k = 0; k < str2.length() - 1; k++) {
            for (int i = k; i < str2.length() - 1; i++) {

                s[count++] = str2.substring(k, i + 2);


            }

        }


        String[] s1 = new String[count];


        int m = 0;
        for (int i = 0; i < count; i++) {


            if (str1.indexOf(s[i]) > 0) {

                s1[m++] = s[i];


            }


        }

        int maxLength = 0;


        for (int j = 0; j < m; j++) {


            if (s1[j].length() > maxLength) {
                maxLength = s1[j].length();
            }


        }
        for (String i : s1) {

            if (i != null) {

                if (i.length() == maxLength) {

                    System.out.println(i);

                }


            }


        }


    }

优化：将2.3.4步操作整合，减少两次循环

    @Test
    public void test4() {


        String str1 = "abcwerthelloyuhelloiodef ";
        String str2 = "cvhellobnm";
        int n = 0;

        for (int i = 0; i < str2.length(); i++) {

            n += i;

        }


        String[] s = new String[n];

        int m = 0;
        int maxLength = 0;
        String[] s1 = new String[n];
        for (int k = 0; k < str2.length() - 1; k++) {
            for (int i = k; i < str2.length() + 1; i++) {

                if (str1.indexOf(str2.substring(k, i)) > 0) {

                    s1[m] = str2.substring(k, i);
                    if (s1[m].length() > maxLength) {
                        maxLength = s1[m].length();
                    }
                    m++;


                }


            }


        }


        for (int i = 0; i < s1.length - 1; i++) {

            if (s1[i] != null) {
                if (s1[i].length() == maxLength) {

                    System.out.println(s1[i]);

                }
            }


        }


    }

方法二：

算法思路：

1、把两个字符串分别以行和列组成一个二维矩阵。

 int maxLen = 0;
        int maxEnd = 0;
        int[][] record = new int[str1.length()][str2.length()];

2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。

if (str1.charAt(i) == str2.charAt(j)) {

                    if (i == 0 || j == 0) {

                        record[i][j] = 0;

                    } else {

                        record[i][j] = record[i - 1][j - 1] + 1;

                    }


                } else {

                    record[i][j] = 0;
                }

3、通过查找出值为1的最长对角线就能找到最长公共子串。

				if (record[i][j] > maxLen) {

                    maxLen = record[i][j];
                    maxEnd = i;

                }
               
String substring = str1.substring(maxEnd - maxLen + 1, maxEnd + 1);
        System.out.println(substring);

全部代码

@Test
    public void test() {


        String str1 = "abcwerthelloyuiodef ";
        String str2 = "cvhellobnm";

        int maxLen = 0;
        int maxEnd = 0;
        int[][] record = new int[str1.length()][str2.length()];


        for (int i = 0; i < str1.length(); i++) {

            for (int j = 0; j < str2.length(); j++) {

                if (str1.charAt(i) == str2.charAt(j)) {

                    if (i == 0 || j == 0) {

                        record[i][j] = 0;

                    } else {

                        record[i][j] = record[i - 1][j - 1] + 1;

                    }


                } else {

                    record[i][j] = 0;
                }

                if (record[i][j] > maxLen) {

                    maxLen = record[i][j];
                    maxEnd = i;

                }


            }

        }
		String substring = str1.substring(maxEnd - maxLen + 1, maxEnd + 1);
        System.out.println(substring);
        }
        

转自：https://blog.csdn.net/qq_25800311/article/details/81607168

方法三：将短的那个串进行长度依次递减的子串与较长的串比较

@Test
    public void work3() {
        String str1 = "abcwerthelloyuiodef";
        String str2 = "cvhellobnm";
        int length = str2.length(); // 用于控制子串的长度

        l1 : while (length >= 0) {
            // 以length为长度从str2中取子串
            int begin = 0; // 开始索引
            int end = begin + length; // 结束索引
            while (end <= str2.length()) { // 只要子串的右边界没有越过短串的右面
                String substring = str2.substring(begin, end);
                if (str1.indexOf(substring) != -1) { //if (长串包含子串) {
                    //总任务完成
                    System.out.println(substring);
                    break l1;
                }
                begin++; // 右移开始索引
                end = begin + length; // 为了保证子串的长度固定, 结束索引也要变化.
            }
            // 长度不合适, 长度--
            length--;
        }
    }