黑马程序员技术交流社区

标题: 找出两个字符串的最大公共子串 [打印本页]

---

作者: Evangelvii    时间: 2012-4-24 16:15
标题: 找出两个字符串的最大公共子串
找出两个字符串的最大公共子串，比如说s1="asdeferdere",s2="cvvsdefrrt"两者的最大公共子串为"sdef"

1. import java.util.LinkedList;
   
2. import java.util.List;
   
3. 
   
4. public class Clothes {
   
5.     public static void main(String[] args) {
   
6.         String s2 = "45aefg1234";
   
7.         String s1 = "12345aesadaefgfewfw";
   
8.         zdggzc(s2, s1);
   
9.     }
   
10. 
    
11.     static void zdggzc(String s1, String s2) {
    
12.         String temp;
    
13.         if (s1.length() < s2.length()) {
    
14.             temp = s1;
    
15.             s1 = s2;
    
16.             s2 = temp;
    
17.             temp = null;
    
18.         }
    
19.         List<String> zdggzc = new LinkedList<String>();
    
20.         int result = 0;
    
21.         StringBuilder maxSubStr = new StringBuilder();
    
22. 
    
23.         for (int i = 0; i <= s1.length() - 1; i++) {
    
24.             char curChar = s1.charAt(i);
    
25.             int indexInS2 = 0;
    
26.             boolean flag = false;
    
27.             while (true) {
    
28.                 if (flag) {
    
29.                     break;
    
30.                 }
    
31.                 if (indexInS2 > s2.length() - 1) {
    
32.                     break;
    
33.                 }
    
34.                 indexInS2 = s2.indexOf(curChar, indexInS2);
    
35.                 if (indexInS2 == -1) {
    
36.                     break;
    
37.                 }
    
38.                 maxSubStr.append(curChar);
    
39.                 int offInS1 = i;
    
40.                 int offInS2 = indexInS2;
    
41.                 while (true) {
    
42.                     offInS1++;
    
43.                     offInS2++;
    
44.                     if (offInS1 > s1.length() - 1 || offInS2 > s2.length() - 1) {
    
45.                         flag = true;
    
46.                         break;
    
47.                     }
    
48.                     if (s1.charAt(offInS1) == s2.charAt(offInS2)) {
    
49.                         maxSubStr.append(s1.charAt(offInS1));
    
50.                     } else {
    
51.                         indexInS2++;
    
52.                         break;
    
53.                     }
    
54.                 }
    
55. 
    
56.                 if (maxSubStr.length() >= result) {
    
57.                     result = maxSubStr.length();
    
58.                     zdggzc.add(maxSubStr.toString());
    
59.                 }
    
60.                 maxSubStr.delete(0, maxSubStr.length());
    
61.             }
    
62.         }
    
63.         for (String string : zdggzc) {
    
64.             System.out.println(string);
    
65.         }
    
66.     }
    
67. }

复制代码

有没有简单的方法

---

作者: 孙天    时间: 2012-4-24 17:58
1。将长度较短作为参照，对其进行取子串，并将其子串在另一个字符串中进行匹配。
                从大往小取，长度依次递减。
        */
        public String getMaxString(String str1,String str2)
        {
                String max="";
                for(int x=0;x<str2.length();x++)
                {
                        String temp1=str2.substring(x);
                        for(int y=temp1.length();y>0;y--)
                        {
                                String temp2=temp1.substring(0,y);       
                                if((str1.indexOf(temp1))!=-1&&temp2.length()>max.length())
                                        max=temp2;
                        }       
                }
                return max;       
        }
        /*
        第二种方式。获取长度最大的子串，进行匹配，不满足，长度依次递次递增减减
        将每一次长度递减的子串全部取出进行匹配。
        */
        public String getMaxString_2(String str1,String str2)
        {
                for(int x=0;x<str2.length();x++)
                {
                        for(int y=0,z=str2.length()-x;z<=str2.length();y++,z++)
                        {
                                String temp=str2.substring(y,z);
                                if(str1.contains(temp))
                                        return temp;
                                //System.out.println(temp);       
                        }       
                }       
                return "";
        }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2