/*
* 需求：求两个字符串的最大相同子串。
* 比如:
*         "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;
        }
}

额，这个算法和穷举差不多吧。我来解释解释。
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。

这个如果玩ACM的要求的话  要用栈的模式匹配来玩.....

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

版主还玩ACM啊，犀利犀利

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


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

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

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循环还可以这么玩，求高手帮助，谢谢
                                }
                        }
                }

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:27
版主还玩ACM啊，犀利犀利

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

其实理解这个也很简单，代码我就不解释了。
主要是想一个思想吧。
这个是双重循环，外次循环是控制查到次数，内层循环是查本次循环内是否包最大字符。

让我们先模拟下人工找字符串中最大相同的步骤吧：
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
其实理解这个也很简单，代码我就不解释了。
主要是想一个思想吧。
这个是双重循环，外次循环是控制查到次数 ...

哥们向你学习了