滚动哈希：我的代码在长字符串中使用模数失败

Question

我想解决 https:/leetcode.comproblemslongest-repeating-substring(最长的重复字符串)我想使用滚动哈希来匹配字符串，但是，当我处理modulo时，我的代码似乎并不工作，对于一个具有所有相同字符的字符串，重复子串的最大长度应该是string.length - 1。

public class Main {
    public static void main(String[] args) {
        String str = "bbbbbbbbbbbbbbbbbbb";
        System.out.println(str.length() - 1);
        Solution s = new Solution();
        System.out.println(s.longestRepeatingSubstring(str));
    }
}
class Solution {
        public int  longestRepeatingSubstring(String S) {
            HashSet<Long> h = new HashSet();
            long mod = (long)1e7 + 7;
            for(int i = S.length() - 1; i >0; i--){
                h = new HashSet();
                long c = 0;
                int j = 0;
                for(; j < i; j ++){
                    c = (c*26 % mod  + S.charAt(j) - 'a')% mod;
                }

                h.add(c);
                for(; j < S.length(); j++){
                    c -= (S.charAt(j - i ) - 'a') * Math.pow(26,i-1)% mod;

                    c = (c*26 % mod + S.charAt(j) - 'a')% mod;

                    if(h.contains(c)){
                        return i;
                    }
                    h.add(c);

                }
            }
            return 0;
        }
    }

我的代码的游乐场。https:/leetcode.complaygroundF4HkxbFQ

Answer 1

我们无法看到你的原始链接，我们需要一个密码.modulo的用法似乎真的很复杂.为什么不试试像这样的东西。

class Scratch {
    // "static void main" must be defined in a public class.
    public static void main(String[] args) {
        String str = "bbaaabbbbccbbbbbbzzzbbbbb";
        System.out.println(str.length() - 1);
        Solution s = new Solution();
        System.out.println(s.longestRepeatingSubstring(str));
    }

    static class Solution {
        public int longestRepeatingSubstring(String s) {
            int max = -1;
            int currentLength = 1;

            char[] array = s.toCharArray();
            for (int index = 1; index < array.length; index++) {
                if (array[index - 1] == array[index]) {
                    currentLength++;
                    max = Math.max(max, currentLength);
                } else {
                    currentLength = 1;
                }
            }
            return max;
        }
    }
}