黑马程序员技术交流社区

标题: 关于获取两个字符串最大相同子串问题——最新版 [打印本页]

---

作者: 郭敏    时间: 2011-9-21 17:45
标题: 关于获取两个字符串最大相同子串问题——最新版
public class StringTest {
       
        public static void main(String[] args) {
                       
                String str1 = "abcdadfkjflsjlfsjfl";
               
                String str2 = "abcefsfsfsjsdf";
               
    System.out.println(GetMaxSubString(str1,str2));
               
        }       
        public static String GetMaxSubString(String s1,String s2) {
               
                String max;
                String min;
               
                max = (s1.length()>s2.length())?s1:s2;
                min = (max==s1)?s2:s1;
               
                for(int i=0;i<min.length();i++) {
                       
                        for(int y=0,z=min.length()-i; z!=min.length()+1; y++,z++) {
                               
                        String temp = min.substring(y,z);
                               
                                if(max.contains(temp))
                                                                  
                                        return temp;               
                        }                                       
                 }                       
                return "";       
        }
}
该程序运行后能顺利查找出str1,str2两个字符串中最大相同子串， 现在问题为：
如何给定的两字符串中最大相同子串有多个，请问该如何实现？

---

作者: 匿名    时间: 2011-9-21 17:57
小弟愚钝，如何给定的两字符串中最大相同子串有多个
这句话我确实无法理解，假如我这样读，如何给，（给什么？）给定，你的意思可能是，如何对给定的两个字符串，此时两个字符串又做了主语，中，你的意思是，两个字符串中的最大相同字串，
至此推断，你的意思是否是：[color=RoyalBlue]如何统计出给定的两个字符串中最大相同字串有多少个？[/color]
是否？
明白了!

---

作者: 匿名    时间: 2011-9-21 18:13
标题: 回复 沙发 的帖子
嘿嘿，:lol 不好意思！ 打错字了, 问题应该是：
如果给定的两个字符串中最大相同子串有多少,该如何实现？ 比如说：
运行此段程序的结果为 abc  ，但通过对str1,str2 两字符串的观察，发现 fsj 也同为str1,str2中 最大相同子串，但该程序无法实现！！！

---

作者: 匿名    时间: 2011-9-21 18:53
标题: 回复 藤椅 的帖子
[code]import java.util.HashSet;
import java.util.Set;

public class StringTest {

        public static void main(String[] args) {

                String str1 = "abcdadfkjflsjlfsjfl";

                String str2 = "abcefsfsfsjsdfjfl";

                Set<String> results = GetMaxSubString(str1, str2);
                for (String result : results) {
                        System.out.println(result);
                }

        }

        public static Set<String> GetMaxSubString(String s1, String s2) {

                Set<String> results = new HashSet<String>();
                // 用来保存查找出来的最大字串.
                String max;
                String min;
                int maxLen = 0;
                // 用来记录最大字串的长度.

                max = (s1.length() > s2.length()) ? s1 : s2;
                min = (max == s1) ? s2 : s1;

                for (int i = 0; i < min.length(); i++) {

                        for (int y = 0, z = min.length() - i; z != min.length() + 1; y++, z++) {

                                String temp = min.substring(y, z);

                                if (max.contains(temp)) {
                                        if ((z - y) > maxLen) {
                                                // z-y得到的就是当前字串的长度,
                                                // 如果当前字串的长度大于保存在results里面的字串的长度,
                                                // 那么就把results里面的字串清空,重新开始记录当前的字串.
                                                maxLen = z - y;
                                                results.clear();
                                                results.add(temp);
                                        } else if ((z - y) == maxLen) {
                                                // 如果查找到得字串和results里面的字串长度一样,
                                                // 那么则将当前字串添加到results当中.
                                                results.add(temp);
                                        }
                                }
                        }
                        if (!results.isEmpty()) {
                                // 当results不为空的时候,就说明已经找到了所有的最大字串.
                                // 因为这个程序是从min长度的字符串向一个长度的字符串查找的.
                                // 所以第一次匹配的字符串,就是最大长度的字串.
                                break;
                        }
                }
                return results;
        }
}[/code]上面是我对开始程序的的一个改进，不知道是不是你想要的结果。

---

作者: 匿名    时间: 2011-9-21 19:03
标题: 回复 板凳 的帖子
:victory: 正是我想要的结果！！ 非常感谢！！

---

作者: 匿名    时间: 2011-9-21 19:07
标题: 回复 报纸 的帖子
不好意思，这个程序我犯了糊涂，其实可以更简单的。我又改了一下，你看看。[code]import java.util.HashSet;
import java.util.Set;

public class StringTest {

        public static void main(String[] args) {

                String str1 = "abcdadfkjflsjlfsjfl";

                String str2 = "abcefsfsfsjsdfjfl";

                Set<String> results = GetMaxSubString(str1, str2);
                for (String result : results) {
                        System.out.println(result);
                }

        }

        public static Set<String> GetMaxSubString(String s1, String s2) {

                Set<String> results = new HashSet<String>();
                // 用来保存查找出来的最大字串.
                String max;
                String min;

                max = (s1.length() > s2.length()) ? s1 : s2;
                min = (max == s1) ? s2 : s1;

                for (int i = 0; i < min.length(); i++) {

                        for (int y = 0, z = min.length() - i; z != min.length() + 1; y++, z++) {

                                String temp = min.substring(y, z);

                                if (max.contains(temp)) {
                                                results.add(temp);
                                }
                        }
                        if (!results.isEmpty()) {
                                // 当results不为空的时候,就说明已经找到了所有的最大字串.
                                // 因为这个程序是从min长度的字符串向一个长度的字符串查找的.
                                // 所以第一次匹配的字符串,就是最大长度的字串.
                                break;
                        }
                }
                return results;
        }
}[/code]

---

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

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