ACM 选手图解 LeetCode 重复的子字符串-阿里云开发者社区

ACM 选手图解 LeetCode 重复的子字符串

2022-04-29 211

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： ACM 选手图解 LeetCode 重复的子字符串

大家好呀，我是帅蛋。

今天解决重复的子字符串，是 KMP 算法的变形题。

这道题比较有意思，把我卡了俩小时，后来是在健身房推胸的时候灵光一闪...

已经很久没碰到要提交两次才能 AC 的题了。

牛皮不多吹，我们来看一下这道题。

LeetCode 459：重复的子字符串

题意

给定一个非空的子字符串，判断它是否可以由它的一个子串重复多次构成。

示例

输入："abab"
输出：True

提示

给定的字符串只含有小写英文字母，并且长度不超过 10000。

题目解析

官方难度评级，本题为简单，我怀疑 LeetCode 是在搞心态...

这要是道简单题，我直播...咳咳...

之前 KMP 算法我们说的是解决模式串在主串中的位置，重复的子字符串这道题不是求子串在主串中出现的位置，而是判断一个字符串是不是由多个重复子串构成。

官方点讲，这是周期性字符串问题，KMP 是解决这类问题的经典解法。

但是虽说是 KMP，但是用到的只是求 next 的那一块，剩下的，得靠推公式...

我直接先来说下公式：

len(s) % (len(s) -  maxLen) = 0

其中 len(s) 为字符串 s 的长度，maxLen 为最长公共前后缀的长度。

所以这个公式翻译一下就是：如果 s 是周期串，那【s 的长度】是【s 的长度减去最长公共前后缀的长度】的倍数，那字符串 s 就是周期串。

至于为什么是这个公式，就得从盘古开天辟地开始了..

有兴趣的去仔细研究下这篇文章的推理，讲的真的非常好，图文并茂，保证认真看完就懂了...

https://writings.sh/post/algorithm-repeated-string-pattern

至于上面所说的最长公共前后缀就是 next。

具体如何求我在之前 KMP 的入门文章中有详细介绍：

ACM 选手带你玩转 KMP 算法！

next 数组是从 0 开始的，且它存的是位置，所以最长公共前后缀的长度应该是 next[len(s) - 1] + 1。

但是只知道公式是不够的，这道题还是会卡住，没错，就是我...

if maxLen == 0 or s[n - 1] != s[n - 1 - maxLen]:
    return False

or 前面那个我就不说了，maxLen == 0 即 next[len(s) - 1] == -1，找无可找，肯定不存在重复。

下面来重点说下 or 后面这个，我就是缺了这行代码。

这是一种特殊的情况，按照我在【KMP 算法入门】文章里讲的 next 求法：

“abab” 的 next 值为 [-1,0,0,1]，“abac” 的 next 值也为 [-1,0,0,1]，前者是周期串，后者不是，但是后者的 next 值和前者一样，都会被算成周期串。

那怎么解决呢？就是加一个限制条件：

s[n - 1] != s[n - 1 - maxLen]

即如果是周期串，那对应位置上的字母应该是一样的，如果对应位置上的字母不一样，那就肯定不是周期串。

大家一定要注意。

代码实现

Python 代码实现

class Solution:
    def getNext(self, s: str):
        # 后缀匹配指向
        i = 0
        # 前缀匹配指向
        j = -1
        # 初始化 next 数组
        next = [-1] * len(s)
        # 此处 next[0] = -1，所以只需要求剩下的 len(T)-1 个即可
        while i < len(s) - 1:
            # j == -1 就是找无可找 or 匹配成功，相同前缀长度增加1
            if j == -1 or s[i] == s[j]:
                i += 1
                j += 1
                next[i] = j
            # 匹配不成功则在前面的子串中继续搜索，直至找不到（即 j== -1 的情况）
            else:
                j = next[j]
        return next
    def repeatedSubstringPattern(self, s: str) -> bool:
        if len(s) == 0:
            return False
        next = self.getNext(s)
        n = len(s)
        # 最长公共前后缀
        maxLen = next[n - 1] + 1
        if maxLen == 0 or s[n - 1] != s[n - 1 - maxLen]:
            return False
        return n % (n - maxLen) == 0

Java 代码实现

class Solution {
    public int[] getNext(String s){
        int i = 0;
        int j = -1;
        int n = s.length();
        int[] next = new int[n];
        next[0] = -1;
        while(i < n - 1){
            if(j == -1 || s.charAt(i) == s.charAt(j)){
                i += 1;
                j += 1;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
        return next;
    }
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        if (n == 0){
            return false;
        }
        int[] next = getNext(s);
        int maxLen = next[n - 1] + 1;
        if(maxLen == 0 || s.charAt(n - 1) != s.charAt(n - 1 - maxLen)){
            return false;
        }
        return n % (n - maxLen) == 0;
    }
}