java最长重复子串

桃扇骨 2022-12-25 00:51 166阅读 0赞

正文在下面，先打个广告：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]  
例如：  
例如字符串 s =“abcdeabc”  
输出：abc

public class Test { 
        public static void main(String[] args) { 
            System.out.println(maxString("ckabcabck"));
            System.out.println(maxString("abdcdyedhjhyed"));
            System.out.println(maxString("abcdeabc"));
            System.out.println(maxString("ckabcabcl"));
    
            System.out.println("-----");
    
            System.out.println(maxString1("ckabcabck"));
            System.out.println(maxString1("abdcdyedhjhyed"));
            System.out.println(maxString1("abcdeabc"));
            System.out.println(maxString1("ckabcabcl"));
        }
    
        //原文：https://blog.csdn.net/qq_14842117/article/details/93887095
        /* 保存s字符串的所有后缀 对所有后缀进行排序（自然排序） 比较排序后的相邻的后缀的最长公共子串（两个后缀从第一个字符开始的就相等得到公共子串），求出最长的公共子串 */
        public static String maxString(String s) { 
            //保存最长公共子串
            String result = "";
            ArrayList<String> list = new ArrayList<>();
            //得到字符串的所有后缀
            for (int i = s.length() - 1; i >= 0; i--) { 
                list.add(s.substring(i));
            }
            Collections.sort(list);
            for (int i = 0; i < s.length() - 1; i++) { 
                String temp = getComlen(list.get(i), list.get(i + 1));
                if (temp.length() > result.length()) result = temp;
            }
            return result;
        }
    
        //得到两个字符串最长公共长度
        public static String getComlen(String str1, String str2) { 
            int i;
            for (i = 0; i < str1.length() && i < str2.length(); i++) { 
                if (str1.charAt(i) != str2.charAt(i)) { 
                    break;
                }
            }
    
            return  str1.substring(0, i);
        }
    
    
        //原文：https://wangwenqiang.blog.csdn.net/article/details/95235285?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control
        public static String maxString1(String str) { 
            if (str == null || str.length() == 0) { 
                return "";
            }
            //假设重复的字符串相隔1,2,3,4,...str.length();
            int k = 0;
            int max = 0;
            int first = 0;
            for (int i = 1; i < str.length(); i++) { 
                //从当前位置开始，将相隔i 的重复的求出来！
                for (int j = 0; j < str.length() - i; j++) { 
                    if (str.charAt(j) == str.charAt(i + j)) { 
                        k++;
                    } else { 
                        k = 0;
                    }
                    if (k > max) { 
                        max = k;
                        first = j - k + 1;//实质为：j-(k-1)
                    }
                }
                k = 0;
            }
    
            return str.substring(first, first + max);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZneWlidXBp_size_16_color_FFFFFF_t_70]: /images/20221120/6c9ece12f61a4e4a82991e921949f1f4.png