java - 最大重复序列而不是最长重复序列

Question

我正在尝试获取字符串中重复次数最多的字符序列。 例如:

输入:

s = "abccbaabccba"

输出:

 2

我已经使用动态规划计算出重复序列，但这会返回最长的重复字符序列。例如:

输入:

s = "abcabcabcabc"

输出:

2   
2(abcabc,abcabc) instead of 4(abc,abc,abc,abc)

这是我填充 DP 表并提取重复序列的代码部分。谁能建议我如何获得重复次数最多的序列？

 //Run through the string and fill the DP table.
        char[] chars = s.toCharArray();
        for(int i = 1; i <= length; i++){
            for(int j = 1; j <= length; j++){
                if( chars[i-1] == chars[j-1] && Math.abs(i-j) > table[i-1][j-1]){
                    table[i][j] = table[i-1][j-1] + 1;
                    if(table[i][j] > max_length_sub){
                        max_length_sub = table[i][j];
                        array_index = Math.min(i, j);
                    }
                }else{
                    table[i][j] = 0;
                }
            }               
        }       
        //Check if there was a repeating sequence and return the number of times it occurred.
        if( max_length_sub > 0 ){
            String temp = s;
            String subSeq = "";
            for(int i = (array_index - max_length_sub); i< max_length_sub; i++){
                subSeq = subSeq + s.charAt(i);
            }
            System.out.println( subSeq );
            Pattern pattern = Pattern.compile(subSeq);
            Matcher  matcher = pattern.matcher(s);
            int count = 0;
            while (matcher.find())
                count++;

            // To find left overs - doesn't seem to matter 
            String[] splits = temp.split(subSeq);
            if (splits.length == 0){
                return count;
            }else{
                return 0;
            }
        }

Answer 1

简单转储，要考虑的最小序列是一对字符(*):

• 遍历整个字符串并获取每对连续的字符，例如使用 for 和 substring 获取字符；
• 计算字符串中该对的出现次数，使用 indexof(String, int) 或正则表达式创建方法 countOccurrences()；和
• 存储最大计数，在循环外使用一个变量 maxCount 和一个 if 来检查实际计数是否更大(或 Math.max() )

(*) 如果“abc”出现 5 次，那么“ab”(和“bc”)也将至少出现 5 次 - 所以只搜索“ab”和“bc”就足够了，不需要检查“abc”

编辑无剩菜，看评论，总结:

• 检查第一个字符是否在整个字符串中重复，如果不重复

• 检查前2个字符是否重复，如果不重复

• 检查 3 ...

至少需要 2 个计数器/循环:一个用于要测试的字符数，第二个用于被测试的位置。可以使用一些算术来提高性能:字符串的长度必须可以被重复字符的数量整除而没有余数。