黑马程序员技术交流社区

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

作者: 贾飞雨    时间: 2012-7-3 15:54
标题: 求两个字符串的最大相同子串,好纠结啊,求高手
本帖最后由 yufeiant 于 2012-7-3 16:52 编辑

/*
* 需求:求两个字符串的最大相同子串。
* 比如:
*         "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
本帖最后由 何旭栋 于 2012-7-3 16:31 编辑

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