重复的子字符串问题

1.重复子字符串问题分析

　　459. 重复的子字符串 - 力扣（LeetCode）

　　有点难度，值得反复刷；本质找 循环子串问题，可以 暴力求解或者移位

2.解法

2.0  暴力求解

　　设 ：字符串 S 由 s'重复构成，则 S=s's's's's's'  (n个s' , s' 长度为 i );

　　则 ：S长度就是 n*i ,那么 我们循环遍历时，固定s'长度 i ，当n%i==0时，判断 s[j] 与 s[j-i] 是否相等；

　　其实也就是从第二个 s' 开始，我往前平移一个s'长度（也就是 i ) , 理论上是不变的【因为循环】

　　所以如果我能找到这样的循环，就说明有重复子串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i * 2 <= n; ++i) 
        {
            //相当于i用来固定前缀的长度的
            if (n % i == 0) {
                bool match = true;
                for (int j = i; j < n; ++j) {
                    if (s[j] != s[j - i]) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
};

2.1 移位法

　原理：

　　假设判断字符串s（n个字符构成）是不是由重复子串构成的，我们先将两个字串拼成一个大的字符串：S = s + s（S 有2n个字符）；

　　字符串拼接的最底层思想是：使用字符串移位来判断字符串是否由重复子串（循环节）构成，因为S这个大的字符串 其实包含了字符串s的所有移位字符串。令字符串字符索引从0开始，[m,n]表示S中索引为m到索引为n的这一段字符，索引为闭区间，则[0,n-1]即S的前一半字符表示原始字符串s；[1,n]表示s右移1位的状态；[2,n+1]表示s右移2位的状态；······；[n,2n-1]即S的后半拉字符串可以理解为s移n位的状态，此时s已经移回了原始的状态了；

　　此外我们不难知道如果一个没有循环节的字符串在移位时必须要右移n次他才能移回它的原始状态，而有循环节的字符串最多只需要n/2次（只有两个循环节，三个和四个同理）；所以当S砍去首尾字符时，对于没有循环节的字符串s，相当于砍去了[0,n-1]的原始状态和[n,2n-1]这个移位n次的又回归原始的状态，我们在[1,2n-2]范围内只能找到s移位1，2，···，n-1位时的状态，所以在[1,2n-2]内是不存在无循环节的s的；但是对于有循环节的s来说，n/2 <= n-1，所以一定存在至少一个移位状态为s，即最少存在一个s（其实对于有循环节的s来说，不考虑移位状态我们也能明白[1,2n-2]内一定至少有一个s，例如对于有两个循环节的s：组成S的前一个s的后一半字符 + 组成S的后一个s的前一半的字符 == s；三个循环节的s更不用说了)

　　代码如下：【KMP的实现见下文】 >  >  > 这里也可以用库函数

    bool repeatedSubstringPattern(string s) {
        string n = s + s;
        n.erase(n.begin());
        n.erase(n.end() - 1);
        if (KMP(n, s))
            return true;
        else
            return false;
    }

2.2 优化KMP算法

　　代码随想录中对于这一部分解释蛮好的，不再重复叙述，参考链接：代码随想录 (programmercarl.com)

　　自实现代码如下，这里只是用到了 KMP前缀表的概念，实际并未完全参照KMP

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int N = s.size();
        int* next = new int[N];
        int j = -1; 
        next[0] = -1;
        for (int i = 1; i < N; ++i)
        {
            while (j >= 0 && s[i] != s[j + 1])
                j = next[j];
            if (s[i] == s[j + 1])
                ++j;
            next[i] = j;
        }
        // next[N - 1] != -1是避免只有一个单独串情况 % 也等于0
        if (next[N - 1]!=-1 &&  N% (N - (next[N-1]+1)) == 0)
            return true;
        else
            return false;
    }
};

2.3 补充KMP算法实现

 bool KMP(string& origin, string& pattern)
    {
        int N = pattern.size();
        int* next = new int[N];
        getNext(pattern, next);
        int j = -1;
        for (int i = 0; i < origin.size(); ++i)
        {
            while (j >= 0 && origin[i] != pattern[j + 1])
                j = next[j];
            if (origin[i] == pattern[j + 1])
                ++j;
            if (j == (N - 1))
                return true;
        }
        return false;
    }
    void getNext(string& s, int* next)  //得到前缀表
    {
        int j = -1;
        next[0] = -1;
        for (int i = 1; i < s.size(); ++i)
        {
            while (j >= 0 && s[i] != s[j + 1])
                j = next[j];
            if (s[i] == s[j + 1])
                ++j;
            next[i] = j;
        }
    }