KMP_leetcode.459.重复的子字符串

🌸题目

🍁给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。
示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

🌸分析

暴力出奇迹，优化见真章！

🌸解法一：暴力解法（直接匹配）

private static boolean repeatedSubstringPattern1(String s) {
       if(s.length() == 0||s.length()==1) return false;
       List<Integer> indexes =new ArrayList<>();
       indexes.add(0);
       //计算出所有有可能的子串长度
       for (int i = 1; i <s.length() ; i++) {
           //和第0个位置的字符相等，且总字符串的长度能够整除当前子串长度
           if(s.charAt(i)==s.charAt(0)
                   &&s.length()%i==0){
               indexes.add(i);
           }
       }
       for (int i = 1; i < indexes.size() ; i++) {
           int length =indexes.get(i);  //当前考虑的子串长度单位
           String str = s.substring(0,length);   //子串
           int j = length;
           //以当前考虑的长度单位进行遍历，如果每隔length的子串都等于str，
           //并且遍历到了字符串末尾，说明结果为true，反之跳出考虑下一种子串长度
           for (; j <s.length() ; j=j+length) {
               if(!s.substring(j,j+length).equals(str))
                   break;
           }
           if(j==s.length())
               return true;
       }
       return false;
}

🌸解法二：暴力解法（枚举）

如果一个长度为n的字符串s可以由它的一个长度为n'的子串s'重复多次构
成，那么:

n—定是n'的倍数;
s'一定是s的前缀;
对于任意的i ∈[n’, 7)，有s[2]= s[i - n']。

也就是说，s中长度为n'的前缀就是s'，并且在这之后的每一个位置上的字符s[i]，都需要与它之前的第n'个字符s[i-n']相同。

因此，我们可以从小到大枚举n'，并对字符串s进行遍历，进行上述的判断。注
意到一个小优化是，因为子串至少需要重复一次，所以n'不会大于n的一半，我
们只需要在[1, n/2]的范围内枚举n'即可。

private static boolean repeatedSubstringPattern(String s) {
       int n = s.length();
       for (int i = 1; i * 2 <= n; ++i) {
           if (n % i == 0) {
               boolean match = true;
               for (int j = i; j < n; ++j) {
                   if (s.charAt(j) != s.charAt(j - i)) {
                       match = false;
                       break;
                   }
               }
               if (match) {
                   return true;
               }
           }
       }
       return false;
   }

🌸解法三：移动匹配

如果您的字符串S包含一个重复的子字符串，那么这意味着您可以多次“移位和换行”您的字符串，并使其与原始字符串匹配。
例如:abcabc

移位一次:cabcab
移位两次:bcabca
移位三次:abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串

基于这个思想，可以每次移动k个字符，直到匹配移动length -1次。但是这样对于重复字符串很长的字符串，效率会非常低。在LeetCode中执行时间超时了。

为了避免这种无用的环绕，可以创建一个新的字符串str;它等于原来的字符串S再加上S自身，这样其实就包含了所有移动的字符串。

比如字符串: S= acd，那么str = S+S = acdacd

acd移动的可能: dac、cda。其实都包含在了str中了。就像一个滑动窗口一开始acd (acd)，移动一次ac(dac)d,移动两次a(cda)cd。循环结束

所以可以直接判断str中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

private static boolean repeatedSubstringPattern2(String s) {
	String str = s + s;
	return str.substring(1, str.length() - 1).contains(s);
}

🌸解法四：KMP（留下了无知的泪水，太难了。）

读者需要注意以下几点:

KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度；
学习 KMP 算法时，一定要理解其本质。如果放弃阅读晦涩难懂的材料（即使大部分讲解 KMP 算法的材料都包含大量的图，但图毕竟只能描述特殊而非一般情况）而是直接去阅读代码，是永远无法学会 KMP 算法的。读者甚至无法理解 KMP 算法关键代码中的任意一行。

由于本题就是在一个字符串中查询另一个字符串是否出现，可以直接套用 KMP 算法。因此这里对 KMP 算法本身不再赘述。读者可以自行查阅资料进行学习。这里留了三个思考题，读者可以在学习完毕后尝试回答这三个问题，检验自己的学习成果：

设查询串的的长度为 n，模式串的长度为 m，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？
如果有多个查询串，平均长度为 n，数量为 k，那么总时间复杂度是多少？
在 KMP 算法中，对于模式串，我们需要预处理出一个fail 数组（有时也称为 next 数组、π 数组等）。这个数组到底表示了什么？

public boolean repeatedSubstringPattern3(String s) {
       return kmp(s + s, s);
   }

   public boolean kmp(String query, String pattern) {
       int n = query.length();
       int m = pattern.length();
       int[] fail = new int[m];
       Arrays.fill(fail, -1);
       for (int i = 1; i < m; ++i) {
           int j = fail[i - 1];
           while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
               j = fail[j];
           }
           if (pattern.charAt(j + 1) == pattern.charAt(i)) {
               fail[i] = j + 1;
           }
       }
       int match = -1;
       for (int i = 1; i < n - 1; ++i) {
           while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
               match = fail[match];
           }
           if (pattern.charAt(match + 1) == query.charAt(i)) {
               ++match;
               if (match == m - 1) {
                   return true;
               }
           }
       }
       return false;
   }

🌸正确性证明

题解出自@LeetCode-Solution

🌸思考题答案

设查询串的的长度为 n，模式串的长度为 m，我们需要判断模式串是否为查询串的子串。那么使用 KMP 算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种分析方法？
- 时间复杂度为 O(n+m)，用到了均摊分析（摊还分析）的方法。
- 具体地，无论在预处理过程还是查询过程中，虽然匹配失败时，指针会不断地根据 fail 数组向左回退，看似时间复杂度会很高。但考虑匹配成功时，指针会向右移动一个位置，这一部分对应的时间复杂度为 O(n+m)。又因为向左移动的次数不会超过向右移动的次数，因此总时间复杂度仍然为 O(n+m)。
如果有多个查询串，平均长度为 n，数量为 k，那么总时间复杂度是多少？
- 时间复杂度为 O(nk+m)。模式串只需要预处理一次。
在 KMP 算法中，对于模式串，我们需要预处理出一个fail 数组（有时也称为next 数组、π 数组等）。这个数组到底表示了什么？
- fail[i] 等于满足下述要求的 x 的最大值：s[0:i]具有长度为 x+1 的完全相同的前缀和后缀。这也是 KMP 算法最重要的一部分

🌸解法五: 优化的KMP

如果读者能够看懂「正确性证明」和「思考题答案」这两部分，那么一定已经发现了方法三中的 KMP 算法有可以优化的地方。即：

在「正确性证明」部分，如果我们设 i 为最小的起始位置，那么一定有 gcd(n,i)=i，即 n 是 i 的倍数。这说明字符串 s 是由长度为 i的前缀重复 n / i次构成；
由于fail[n−1] 表示 s 具有长度为 fail[n−1]+1 的完全相同的（且最长的）前缀和后缀。那么对于满足题目要求的字符串，一定有 fail[n−1]=n−i−1，即 i=n−fail[n−1]−1；
对于不满足题目要求的字符串，n 一定不是 n −fail[n−1]−1 的倍数

上述所有的结论都可以很容易地使用反证法证出。

因此，我们在预处理出fail 数组后，只需要判断 n 是否为 n - fail[n−1]−1 的倍数即可。

public boolean repeatedSubstringPattern4(String s) {
    return kmp(s);
}

public boolean kmp(String pattern) {
    int n = pattern.length();
    int[] fail = new int[n];
    Arrays.fill(fail, -1);
    for (int i = 1; i < n; ++i) {
        int j = fail[i - 1];
        while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
            j = fail[j];
        }
        if (pattern.charAt(j + 1) == pattern.charAt(i)) {
            fail[i] = j + 1;
        }
    }
    return fail[n - 1] != -1 && n % (n - fail[n - 1] - 1) == 0;
}

题解出自LeetCode-Solution

🌸题目

🌸分析