1668. 最大重复子字符串

1668. 最大重复子字符串

方法一：暴力枚举

class Solution {
   public int maxRepeating(String sequence, String word) {
        char[] ch1 = sequence.toCharArray();
        int res = 0;
        StringBuilder sb = new StringBuilder(word);
        while(sb.length() <= sequence.length()) {
            if (isEqual(ch1, sb.toString().toCharArray())) {
                res ++;
                sb.append(word);
            } else {
                break;
            }
        }
        return res;
    }
    public boolean isEqual(char[] ch1, char[] ch2) {
        if (ch2.length > ch1.length){
            return false;
        }

        for(int k = 0; k < ch1.length - ch2.length + 1; k ++) {
            int i = k, j = 0;
            while (i < ch1.length && j < ch2.length) {
                if (ch1[i] == ch2[j]) {
                    i++;
                    j++;
                }else{
                    break;
                }
            }
            if (j == ch2.length) return true;
        }

        return false;
    }
}

方法二：DP + KMP

KMP模板

for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j > 0 && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j > 0 && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}