字符串——重复的子字符串

459. 重复的子字符串

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

1 <= s.length <= 104
s 由小写英文字母组成

思路

暴力

这个暴力还是有点技巧的

核心思想：把一段字符串（长度为n），均分成长度为i的子字符串，i从长度1开始，n/2结束（重复的子字符串至少出现两次，大于n/2就超了），比对每份相对应的位置字符（第一份为母本，第二份比对第一份；第二份对的上，就第三份比对第二份，直到最后一份），重复的子字符串一定是有从头开始的（前缀），或从尾部开始（后缀）

n%i有余如图（明显不可能）

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n=s.size();
        for(int i=1;i*2<=n;i++)//从长度为1开始均分
        {
            if(n%i==0)//可以均分才可能由子字符串组成，如5%2=1，子字符串为2不可能组成5
            {
                bool match=true;
                for(int j=i;j<n;j++)//将所有均分的子字符串与前一个比对
                {
                    if(s[j]!=s[j-i]){
                        match=false;
                        break;
                    }
                }
                if(match)//bool match=true;match参数位置放好，不然读取参数出现区域快问题
                return match;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

移动匹配

字符串s与相同字符串s拼接在一起

若s由子字符串重复组成，结果如下图，蓝色部分可以组成新的s

若s不能由子字符串重复组成，结果如下图，不可能找到s

由上两张图可以得到思路：
构建一个s+s新字符串t，从中找到新的s，避免找到原s，删除t的第一个字符和最后一个字符；或寻找范围内不包括第一个字符和最后一个字符

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t=s+s;
        t.erase(t.begin());t.erase(t.end()-1);
        if(t.find(s)!=t.npos) return true;//npos表示为没找到的意思，不等于没找到，就是找到了
        return false;
    }
};
1
2
3
4
5
6
7
8
9

t.find(s)没找到返回的是-1，t.npos表示就是-1，你将t.npos换成-1一样运行成功

KMP

KMP算法说明+解释
这道题使用KMP算法是使用它的一种特殊情况

看图中，绿色为重复的部分
前缀表的数值是部分匹配的下标跳转

问题：部分匹配指的是什么

图中下标4位置的2，意思为当下标5的f不匹配时，说明要重新匹配，但开头aa和3、4的aa一样，已经匹配过，于是重新匹配时，上次匹配3、4的a、a可以匹配，换成1、2的a、a效果一样，所以从下标2开始匹配。
可以理解为前缀表中的值为重复字符的个数，一直重复数值就一直增加
字符串大小-重复数值=可能的重复子字符串

看图中，前缀表中的值表示匹配上的位置，当字符串由重复子字符组成，前缀表最后的值不可能为0，

6-4=2,可能长度为2，因为可能构成重复子字符串只可能为前缀，所以就已知可能的子字符串，不用遍历所有子字符串进行比较。

代码

class Solution {
public:
    void getNext(int* next,string &s)//构建next前缀表，j=0式
    {
        int j=0;
        next[0]=j;
        for(int i=1;i<s.size();i++)
        {
            while(j>0 && s[i]!=s[j])
            {
                j=next[j-1];
            }
            if(s[i]==s[j])
            {
                j++;
            }
            next[i]=j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next,s);
        if(next[s.size()-1]==0)//最后一位为0，说明没有部分重复，就不可能由子字符串组成
            return false;
        int length=s.size()-next[s.size()-1];//可能子字符串长度
        if(s.size()%length!=0)//n个子字符串长度不等于字符串长度，不可能构成
            return false;
        for(int i=length;i<s.size();i++)//比较子字符串和字符串，判断是否由重复子字符串构成
        {   
            bool match=true;
            if(s[i]==s[i-length])
            {
                match=true;
                break;
            }
            else
                match=false;
            return match;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42