1. /*
   
2. 获取两个字符串中最大相同子串。第一个动作：将短的那个串进行长度一次递减的子串打印。
   
3.         "abcwerthelloyuiodef"
   
4.         "cvhellobnm"
   
5. 
   
6. 模拟一下：
   
7. 第一趟：
   
8. 最大子串：cvhellobnm
   
9.           ↑--------↑
   
10. 在长字符串中查找
    
11. abcwerthelloyuiodef
    
12. ↑--------↑
    
13. abcwerthelloyuiodef
    
14. ↑--------↑
    
15. abcwerthelloyuiodef
    
16.   ↑--------↑
    
17. abcwerthelloyuiodef
    
18.    ↑--------↑
    
19. abcwerthelloyuiodef
    
20.     ↑--------↑
    
21. abcwerthelloyuiodef
    
22.      ↑--------↑
    
23. abcwerthelloyuiodef
    
24.       ↑--------↑
    
25. abcwerthelloyuiodef
    
26.        ↑--------↑
    
27. abcwerthelloyuiodef
    
28.         ↑--------↑
    
29. abcwerthelloyuiodef
    
30.          ↑--------↑
    
31. 没有找到。
    
32. 第二趟：
    
33. 最大子串1：cvhellobnm
    
34.            ↑-------↑
    
35. 最大子串2：cvhellobnm
    
36.             ↑-------↑
    
37. 继续在长串中匹配，如果没有找到。
    
38. 第三趟：
    
39. 最大子串1：cvhellobnm
    
40.            ↑------↑
    
41. 最大子串2：cvhellobnm
    
42.             ↑------↑
    
43. 最大子串3：cvhellobnm
    
44.              ↑------↑
    
45. 继续在长串中匹配，如果没有找到。
    
46. 第四趟：
    
47. 最大子串1：cvhellobnm
    
48.            ↑-----↑
    
49. 最大子串2：cvhellobnm
    
50.             ↑-----↑
    
51. 最大子串3：cvhellobnm
    
52.              ↑-----↑
    
53. 最大子串4：cvhellobnm
    
54.               ↑-----↑
    
55. ······
    
56. 如果找到了则停止，返回最大相同子串；
    
57. 如果最大子串为""，则放回没有最大相同子串。
    
58. 
    
59. 根据上面模拟过程，可以得到以下思路：
    
60. 第一步：在两个字符串中选取长度短的那个字符串为key，长的那个为str；转到第二步。
    
61. 第二步：从左到右，在str中匹配key，如果成功，转第四步；否则，转第三步。
    
62. 第三步：将key长度减一，得到多个长度相同的子串，每个子串依次执行第二步。当key为空串的时候，转到第五步。
    
63. 第四步：匹配成功，结束匹配。
    
64. 第五步：匹配失败。
    
65. 
    
66. 点评：第三步没有分析清楚，所以没有写出来。
    
67. key.length()-0  子串1个
    
68. key.length()-1  子串1+1个
    
69. key.length()-2  子串1+1+1个
    
70. key.length()-3  子串1+1+1+1个
    
71. 可以观察发现，
    
72. 
    
73. 第三步用大循环嵌套小循环实现。
    
74. 大循环为key的
    
75. */
    
76. class getMaxSubstringDemo
    
77. {
    
78.         public static void main(String[] args)
    
79.         {
    
80.                 String str1 = "abcwerthelloyuiodef";
    
81.                 String str2 = "cvhellobnm";
    
82. 
    
83.                 System.out.println( getMaxSubstring(str1,str2));
    
84.         }
    
85. 
    
86.         //匹配最大相同子串
    
87.         public static String getMaxSubstring(String str1,String str2)
    
88.         {
    
89.                 // 比较两个字符串长度，长的为str，短的为key
    
90.                 String str = (str1.length()>str2.length())?str1:str2;
    
91.                 String key = (str==str1)?str2:str1;
    
92.                
    
93.                 for(int i = 0;i < key.length(); i++)
    
94.                 {
    
95.                         for(int j = 0,k = key.length()-i; k !=key.length()+1;j++,k++)//j为key的头指针，k为key的尾指针
    
96.                         {
    
97.                                 //设置一个临时变量，存储最大相同子串
    
98.                                 String temp = key.substring(j,k);
    
99.                                 if(str.indexOf(temp) != -1)
    
100.                                         return temp;
     
101.                         }
     
102.                 }
     
103.                 return "";
     
104. 
     
105.                
     
106.                 /*错误思路，未解决问题
     
107.                 //key在str中的位置
     
108.                 int index = str.indexOf(key);
     
109. 
     
110.                 /2 用方法int indexOf(String str)进行判断key是否被包含在str中
     
111.                 当key不为空，且在str中没找到key时，执行循环。
     
112.                 当key为空，就结束循环。
     
113.                 当key不为空，inex!=-1时，说明找到了最大相同子串，停止循环。
     
114.                 /
     
115.                 while(key.length() != 0 && index ==-1)
     
116.                 {
     
117.                         index = str.indexOf(key);
     
118.                 }
     
119. 
     
120.                 //key的长度减一，得到多个相同长度的key
     
121.                 public static String getKeySubstring(String key)
     
122.                 {
     
123.                         for(int i = 0;i < key.length(); i++)
     
124.                         {
     
125.                                 for(int j = 0;j < key.length()-i && j != key.length();)
     
126.                         }
     
127.                 }
     
128.                 */
     
129.        
     
130.         }
     
131. }
     

复制代码

思路还不是很清晰，暂时先这样了，等想清楚了，再写一遍！

刚才的方法有2个漏洞 删除
用dp可以做到O(m*n) 级别的效率：

1. 
   
2.         public static String maxSubString(String st1, String st2) {
   
3.                 char[] x=st1.toCharArray(),y=st2.toCharArray();
   
4.                 int maxlen =0, maxindex = 0,xlen=x.length,ylen=y.length;
   
5.                 int [][] dp=new int[xlen][ylen];
   
6.                 for (int i = 0; i < xlen; ++i) {
   
7.                         for (int j = 0; j < ylen; ++j) {
   
8.                                 if (x[i] == y[j]) {
   
9.                                         if (i>0 && j>0) {
   
10.                                                 dp[i][j] = dp[i - 1][j - 1] + 1;
    
11.                                         }
    
12.                                         if (i == 0 || j == 0) {
    
13.                                                 dp[i][j] = 1;
    
14.                                         }
    
15.                                         if (dp[i][j] > maxlen) {
    
16.                                                 maxlen = dp[i][j];
    
17.                                                 maxindex = i + 1 - maxlen;
    
18.                                         }
    
19.                                 }
    
20.                         }
    
21.                 }
    
22.                 return new String(x,maxindex,maxlen);
    
23.         }

复制代码

我这个方法做了2重循环，效率还是很低 ，求高手

看得头晕····

{:3_46:}都来看看啊

还没学到，了解一下

public class getString {

        public static void main(String[] args) {
               
                String str2 = "abcwerthelloyuiodef";
                String str1 = "cvhellobnm";
               
                getStr(str1, str2);
                       

        }

        public static void getStr(String str1, String str2) {
               
                String temp = null;
                //确保str1是较长的字符串，str2是较短的字符串
                if(str1.length()<str2.length())
                {
                        temp = str1;
                        str1 = str2;
                        str2 = temp;
                       
                }
                for(int i=str2.length();i>=0;i--) {
                        for(int j=0;j<=str2.length()-i;j++) {
                               
                                temp = str2.substring(j, j+i-1);
                                if(str1.contains(temp)) {
                                        System.out.println(str1+"和"+str2+"的最长字串是： "+temp);
                                        i = -1;  //跳出外循环
                                        break;
                                }
                        }
                }
               
//                System.out.println(str1+"和"+str2+"没有最长字串");
        }

}