黑马程序员技术交流社区

标题: 求两个字符串的最大相同子串，好纠结啊，求高手 [打印本页]

---

作者: 贾飞雨    时间: 2012-7-3 15:54
标题: 求两个字符串的最大相同子串，好纠结啊，求高手


/*
* 需求：求两个字符串的最大相同子串。
* 比如:
*         "sadabcdfghjkl"
"werabcdtyu"
*/
public class StringTest3 {

        public static void main(String[] args) {
                String s1 = "sadabcdfghjkl";
                String s2 = "werabcdtyu";
                System.out.println(getMaxSubString(s1,s2));
        }
        public static String getMaxSubString(String s1, String s2) {
                String max, min;
                max = s1.length() > s2.length() ? s1 : s2;
                min = s1.length() <= s2.length() ? s1 : s2;
                for(int x=0; x<min.length(); x++){
                        for(int y=0,z=min.length()-x; z<=min.length(); y++,z++){
                                String temp = min.substring(y,z);
                                if(max.contains(temp)){
                                        return temp;//这个算法这里怎么都不明白，没有想到for循环还可以这么玩，求高手帮助，谢谢
                                }
                        }
                }
                return null;
        }
}

---

作者: 刘鹏程    时间: 2012-7-3 16:17
额，这个算法和穷举差不多吧。我来解释解释。
for(int x=0; x<min.length(); x++){
                        for(int y=0,z=min.length()-x; z<=min.length(); y++,z++){
                                String temp = min.substring(y,z);
                                if(max.contains(temp)){
                                        return temp;                                }
                        }
                }
这段代码，最外面层循环for(int x=0; x<min.length(); x++)其实就是为了里面z=min.length()-x做的循环次数，就是首先在两个字符串中小的中找他们的相同子串，这里就是从min.length()长度开始找，一直找到长度为1的相同子串。也就是外面那层循环是控制找相同子串时子串的长度。
里面那层循环是 for(int y=0,z=min.length()-x; z<=min.length(); y++,z++)是在min字符串中从第一个字符开始得到长度为min.length-x的子串，并在max字符串中查看是否也有该子字符串。如果存在则返回子字符串。
String temp = min.substring(y,z);是找min中下标y到z的子字符串。
max.contains(temp);若temp是max的子字符串则返回true，否则返回false。

---

作者: 蒋映辉    时间: 2012-7-3 16:26
这个如果玩ACM的要求的话  要用栈的模式匹配来玩.....

---

作者: 刘鹏程    时间: 2012-7-3 16:27

蒋映辉 发表于 2012-7-3 16:26
这个如果玩ACM的要求的话  要用栈的模式匹配来玩.....

版主还玩ACM啊，犀利犀利

---

作者: Forever。    时间: 2012-7-3 16:30
看了一会儿 看出了点眉目。这个嵌套for循环是这样的，他以长度小的字符串为基础循环，从最大范围去和较长的字符串进行对比，然后范围不断变小，比如较小的字符串长度为10，那么第一次他先对比整个字符，第二次对比9个字符，第三次对比8个……，
控制对比长度的就是最外层的for循环。而里面的for循环的任务是，将开始和结束的地点遍历。也就是比如说：
字符串长度为11     第一次对比11个字符，所以运行一次里面的for循环就结束了。开始结束的地方是0，10
                          第二次对比10个字符，      开始结束的地方为0,9     1,10      一共循环两次。
                          ………………
以此类推。


而对比字符串的代码就是if(max.contains(temp))这里，不用多讲就是一个方法而已。

难懂的地方实际上还是第二个for循环，而第二个for循环的关键控制在z难理解。z指的是字符的结束位置。其实大家多看几遍便会理解了到底是怎么回事。    楼主不懂可以再问我。

---

作者: 何旭栋    时间: 2012-7-3 16:30


for(int x=0; x<min.length(); x++){
//这里x定义了所取需要比较的子字符串长度，子字符串长度为min.length()-x ，随着x的自增，子字符串长度从min.length() ~0
                        for(int y=0,z=min.length()-x; z<=min.length(); y++,z++){
                        //y为子字符串temp在min中的头坐标，z为结束坐标，每比较一次y和z自增，向后偏移一位，但是temp长度不变
                        //这样先从min中取所有长度为z-y(min.length()-x )的子字符串和max比较，没有的话退出当前循环，x自增，长度z-y也就减1
                        //又一次取z-y长度的子字符串和 max比较，知道找到包含的字符串返回。
                                String temp = min.substring(y,z);
                                if(max.contains(temp)){
                                        return temp;//这个算法这里怎么都不明白，没有想到for循环还可以这么玩，求高手帮助，谢谢
                                }
                        }
                }

---

作者: 王明明    时间: 2012-7-3 16:31
public class StringTest3 {

        public static void main(String[] args) {
                String s1 = "sadabcdfghjkl";
                String s2 = "werabcdtyu";
                System.out.println(getMaxSubString(s1,s2));
        }
        public static String getMaxSubString(String s1, String s2) {
                String max, min;
                max = s1.length() > s2.length() ? s1 : s2;
                min = s1.length() <= s2.length() ? s1 : s2;//这个min 跟max 是为了判断获取的2个字符串 把长的赋值给max短的赋值给min 减少比较次数               
                for(int x=0; x<min.length(); x++){
                        for(int y=0,z=min.length()-x; z<=min.length(); y++,z++){// 老师讲的这个先比较整个的min字符 也就是0角标到min.length()角标                              
                                     String temp = min.substring(y,z);                           //第二次是min.length-1个字符来比较 也就是werabcdty erabcdtyu                                
                                     if(max.contains(temp)){                                          //第三次是min.length-2个字符来比较 也就是werabcdt erabcdty rabcdtyu 以此类推的...
                                        return temp;//这个算法这里怎么都不明白，没有想到for循环还可以这么玩，求高手帮助，谢谢
                                }
                        }
                }
                return null;
        }
}

---

作者: 李伟    时间: 2012-7-3 16:50

---

作者: 蒋映辉    时间: 2012-7-3 16:59

刘鹏程 发表于 2012-7-3 16:27
版主还玩ACM啊，犀利犀利

就大一的时候玩了一下   知道点皮毛而已.....

---

作者: 陈淑飞    时间: 2012-7-3 17:11
其实理解这个也很简单，代码我就不解释了。
主要是想一个思想吧。
这个是双重循环，外次循环是控制查到次数，内层循环是查本次循环内是否包最大字符。

让我们先模拟下人工找字符串中最大相同的步骤吧：
1. 先把最多的，比如上面s2串10个字符 都丢进去比是否 相同。 先理解成。利益最大化。
2. 再把第二多的，也就是可能有9个字符相同的，丢进去找 是否相同。
3. 我最多找10次吧，所以外层循环就出来 小于 最小串的长度。

因为我每次循环找都是利益最大化，比如
0次，是找10个串，只需要比(0,10)就OK了。找不着。重来按9个串标准找
1次  是找9个串 只要比(0,9) 和(1,10)就OK了。找不着。重来按8个串标准找
2次  是找8个串 只要比(0,8) 和(2,9)和(3,10)就OK了
...

这样推算内层循环自然就了来了，内层中必须每次循环从0开始，且会自加，但同时截取的长度也要固定，即截取的最后一位位置也要自加才行。


欧了没？

其实，这个问题我最先想到的是，用选择排序的那套思想，在求最大相同字符串之前，先用定义个字符串，MaxStr用来保证每次找到的临时最大字符串。

然后通过双重循环找，将每次找到的相同字符串与最大的MaxStr对比，看哪个长度长，长度长的保存在maxStr。循环结果 返回MaxStr即可。

但这种方式，显然没有LZ给出的算法用效率，呵呵。 顶一个，学习了。

---

作者: 贾飞雨    时间: 2012-7-3 17:11
虽然是明白了，但是下次让我写估计还是会写不出来，哎，谢谢各位

---

作者: 贾飞雨    时间: 2012-7-3 17:11
虽然是明白了，但是下次让我写估计还是会写不出来，哎，谢谢各位

---

作者: 贾飞雨    时间: 2012-7-3 17:18

陈淑飞 发表于 2012-7-3 17:11
其实理解这个也很简单，代码我就不解释了。
主要是想一个思想吧。
这个是双重循环，外次循环是控制查到次数 ...

哥们向你学习了

---

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

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