package tek;

　　Java算法——求出两个字符串的最长公共字符串

/**

 * @Title: 问题：有两个字符串str1和str2，求出两个字符串中最长公共字符串。

 * @author 匹夫(在YW的数据基础上再次延伸)

 * @date 2017年4月19日 下午8:08:37

 */

public class Demo1 {

    /*

    //减0 个字符  内循环1次

    k2.substring(0, 7);//外循环第1次_内循环第1次

    //减一个字符  内循环2次

    k2.substring(0, 6);//外循环第2次_内循环第1次

    k2.substring(1, 7);//外循环第2次_内循环第2次

    //减两个字符 内循环3次

    k2.substring(0, 5);// 外循环第3次_内循环第1次

    k2.substring(1, 6);// 外循环第3次_内循环第2次

    k2.substring(2, 7);// 外循环第3次_内循环第2次

    //减3个字符  内循环4次

    k2.substring(0, 4);// 外循环第4次_内循环第1次

    k2.substring(1, 5);// 外循环第4次_内循环第2次

    k2.substring(2, 6);// 外循环第4次_内循环第3次

    k2.substring(3, 7);// 外循环第4次_内循环第4次

*/

    public static void main(String [] args){

        String k1 = "10101121018";

        String k2 = "101210182";

        String max = null;

        String max_str = null;

        String min_str = null;

        if(k1.length()==k2.length()){

            max_str = k1;

            min_str = k2;

        }else if(k1.length()>k2.length()){

            max_str = k1;

            min_str = k2;

        }else{

            max_str = k2;

            min_str = k1;

        }

        int index = 0;

        for(int x=min_str.length();x>=0;x--){

            int b = x;

            boolean flag = false;

            for(int y=0;y<=min_str.length()-x;y++){

                index++;

                int v = y;

                String wait_max = min_str.substring(v, b);

                if(max_str.contains(wait_max)){

                    max = wait_max;

                    flag = true;

                    break;

                }

                b++;

            }

            if(flag){

                break;

            }

        }

        System.out.println(index);

        System.out.println(max);

    }

}

String ms = "01012101121301";

String ds = "0121121301";

0121121301

ms.contain(ds.substring(x,y));

x

思路2

10个字符1次

1    0121121301    10    ms.contain(ds.substring(0,10));

9个字符串2次

2    012112130    9    ms.contain(ds.substring(0,9));

3     121121301    9    ms.contain(ds.substring(1,10));

8个字符3次

4       01211213    8    ms.contain(ds.substring(0,8));

5        12112130    8    ms.contain(ds.substring(1,9));

6       21121301    8    ms.contain(ds.substring(2,10));

7个字符4次

7    0121121        7    ms.contain(ds.substring(0,7));

8     1211213    7    ms.contain(ds.substring(1,8));

9      2112130    7    ms.contain(ds.substring(2,9));

10       1121301    7    ms.contain(ds.substring(3,10));

思路1

String temp_max = 0121,

int x = 0;

int y= 10;

ms.contain(ds.substring(x,y));

1    0121121301    ms.contain(ds.substring(0,10));

2    012112130     ms.contain(ds.substring(0,9));

3    01211213      ms.contain(ds.substring(0,8));

4    0121121       ms.contain(ds.substring(0,7));

5    012112        ms.contain(ds.substring(0,6));

6    01211         ms.contain(ds.substring(0,5));

7    0121          ms.contain(ds.substring(0,4));

8    121121301     ms.contain(ds.substring(1,10));

9    12112130      ms.contain(ds.substring(1,9));

10    1211213      ms.contain(ds.substring(1,8));

11    121121       ms.contain(ds.substring(1,7));

12    12112        ms.contain(ds.substring(1,6));

13    1211         ms.contain(ds.substring(1,5));

14    121          ms.contain(ds.substring(1,4));

15    21121301    ms.contain(ds.substring(2,10));

16    2112130     ms.contain(ds.substring(2,9));

17    211213      ms.contain(ds.substring(2,8));

18    21121       ms.contain(ds.substring(2,7));

19    1121301        ms.contain(ds.substring(3,10));