(第15天)【leetcode题解】459、重复的子字符串

459、重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

暴力匹配

思路

推理

如果存在这样的子串，那么这个子串一定是s的前缀。
s的长度n一定是子串长度n1的整数倍
s中的元素s[i]与往前移n1的元素s[i-n1]相同

方法

因此从小到大枚举出所有可能的子串长度n1，再对这个子串进行上述的判断即可。
优化：这个子串至少要在s中重复一次，所以n1的范围为[1,n/2]。

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        //i代表子串的长度，应从1开始
        for (int i = 1; i <= n / 2; i++) {
            //判断该子串是否为目标子串
            if (n % i == 0) {
                bool match = true;
                //判断之后的字符往前移子串长度i之后是否相等
                //从子串之后开始遍历整个字符串
                for (int j = i; j < n; j++) {
                    if (s[j] != s[j - i]) {
                        match = false;
                        break;
                    } 
                }
                if (match) return true;
            }
        }
        return false;
    }
};

时间复杂度：O(n²)；枚举子串的时间复杂度为O(n)，遍历判断子串的时间复杂度为O(n)。
空间复杂度：O(1)；

字符串匹配

思路

如果s满足题目要求，那么s具有以下性质：

设s的长度为n，子串长度s1为n1.
可以把s写成n/n1个子串s1排列的形式： s——>s1s1s1s1…
那么把第一个s1移到最后面，字符串s不变

根据性质，可以证明：

因为1 <= n1 < n，那么把两个字符串s连在一起得到S
把连在一起后的字符串S移除前后第一个元素
这时，字符串s一定是拼接串S的子串

根据证明结果，得到方法：

拼接两个字符串s
移除第一个和最后一个字符
如果s是其中的子串，则满足题目要求

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

与暴力匹配的不同

通过推理，得到一种满足要求是的情况，只要针对这个情况进行判断即可。

KMP解法

思路

假设推理

假设这个文本串由重复子串组成
找到这个文本串的最长公共前后缀
文本串切割掉最长公共前后缀，剩下的就是重复子串

可用的结论

设文本串s由n个长度为x的子串组成，则文本串全长为nx。
最长公共前后缀由m个长度为x的子串组成，长度为mx。
则重复子串长度为(n-m)x。n-m=1
当全长nx对重复子串长度(n-m)x取余等于0时(即nx % (n-m)x == 0 or nx % x == 0)，证明(n-m)x代表的子串为重复子字符串。

方法

求出next数组，next数组长度为len
使用next数组存储文本串中最长公共前后缀的长度next[len - 1]
如果 len % (len -next[len - 1]) == 0，则表明存在重复子字符串

代码

class Solution {
public:
    //得出next数组
    void getNext(int* next, string& s) {
        //初始化
        int j = 0;//前缀末尾从0开始
        next[0] = j;

        //从长度为2的子串开始求最长公共前后缀长度
        for (int i = 1; i < s.size(); i++) {
            //前后缀末尾不匹配时
            while (j >0 && s[i] != s[j]) j = next[j - 1];//j回退
            //前后缀末尾匹配时
            if (s[i] == s[j]) {
                j++;//j(和i)往后移一位
            }
            next[i] = j;//下标j为当前子串(末尾下标为i)的最长公共前后缀长度
        }
    }

    bool repeatedSubstringPattern(string s) {
        int next[s.size()];//创建长度为字符串长度的前缀表
        getNext(&next[0], s);

        //使用最长公共前后缀长度判断是否由重复的子字符串组成
        int len = s.size();
        //next[len - 1] == 0时，证明整个字符串最长公共前后缀长度为0
        //根据推理得出的结论:当len % (len - next[len-1]) == 0 时证明(有重复的子字符串/最后一段字符串为重复子字符串)
        if (next[len - 1] != 0 && len % (len - next[len-1]) == 0) return true;
        return false;
    }
};