代码随想录 | Day10 | 字符串：KMP算法&&找出字符串中第一个匹配项的下标&&重复的子字符串

主要学习内容：

1.KMP算法

2.应用KMP算法解题

KMP算法

关键点：

1.前后缀定义

前缀：包含首字母的所有子串

后缀：包含尾字母的所有子串

2.最长的相等的前后缀的定义

当前字母的最长的相等前后缀看的是不包含该字母的前面的字符串

1
2
3
4
举例：
a a b a a f
f的最长的相等的前后缀看的是a a b a a 即为2
相等的最长前缀和后缀分别是 a a 和 a a

3.next数组

作用是记录当前的字符如果不匹配那么下一次开始匹配的位置

而最长的相等的前后缀的长度就是下一次开始匹配的位置

1
2
3
4
5
举例：
模式串：a a b a a b a a f 
匹配串：a a b a a f
    
刚刚知道了匹配串f的最长的相等前后缀长度为2，则在b!=f的时候，下一次开始匹配的位置就是匹配串中的b

4.next数组和模式串无关，只和自身字符串相关

5.next数组求解代码

就是求解每个元素的最长相等前后缀的长度

定义两个循环因子i，j

i定义为后缀子串的末尾，i的初始化为1，j定义为前缀子串的末尾，初始化为0

s表示为要求的next数组的字符串

1
2
3
4
5
6
7
8
9
10
11
/*分为两种情况

第一种是s[i]!=s[j]即前后缀不相等
此时后缀末尾j就要回退到next[j-1]即j=next[j-1];
注意next数组的定义，虽然我们这时是在求next数组，但其实就是把0-i当做模式串，0-j当做文本串，来进行的回退，用到的next数组只有我们已经求出来的
即next[0-j]就是0-j这个子串的next数组


第二种就是s[i]==s[j]即前后缀相等
那就j++;前缀子串末尾向后移动

整个过程分为四步

  1. next数组初始化

    next[0]=0，因为第一个元素没有相等的前后缀

​ 2.处理前后缀不同

​ 可能回退后还是不同所以用while，回退到j=0就没有退路了，所以j>0

​ 3.处理前后缀相同

​ 4.更新next数组

​ next[i]=j;执行完上面两种情况后j就是当前下标i的元素的相等最长前后缀的长度

这里推荐在代码随想录的视频上看一遍模拟运行的过程会比较好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void getNext(vector<int> &next, const string& s) {
        int j=0;
    //next数组初始化，第一个元素没有相等的前后缀
        next[0]=0;
        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数组
            next[i]=j;
        }
    }

最最最难理解的点就是前后缀不同的情况，把这个搞懂剩下的就迎刃而解了

自己手敲的易错点：i初始化为1才对

28.找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

思路：

i，j分别指向模式串和文本串

1.找到next数组

2.遇到不一样的就根据next数组进行回退

3.一样的话，i，j就继续一起向后移动即可

4.当j和文本串大小相同时说明已经匹配到了答案，就找到了结果，然后返回第一个元素所在的位置即可

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
class Solution {
public:
    //next数组
    void getNext(vector<int> &next, const string& s) {
        int j=0;
        next[0]=0;
        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;
        }
    }
    int strStr(string haystack, string needle) {
        vector<int> next(needle.size(),0);
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
            //两个元素不同
            while(j>0&&haystack[i]!=needle[j])
                j=next[j-1];
            //两个元素相同，一起向后移动
            if(haystack[i]==needle[j])
                j++;
           	//找到答案返回
            if(j==needle.size())
                return i-needle.size()+1;
        }
        return -1;
    }
};

459.重复的子字符串

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

解法一：KMP

思路：

1.求解出next数组

2.最长的前缀和最长的后缀的差集就是最小重复单元的长度

20220728205249

推理过程请看代码随想录视频

知道这是最小重复单元后只需要用最小重复单元和字符串长度取余就可以判断是否可以由这些子串构成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int j=0;
        vector<int> next(s.size(),0);
        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;
        }
        int len = s.size();
        //取余过程
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

解法二：移动匹配

**思路：**如果一个字符串s可以由重复单元组成那么将两个s拼接到一起，中间势必会出现一个s是由这些重复单元组成的

然后在新的字符串里面找原来的s，能找到就是可以由重复子串组成

注意点：要去掉头部和尾部元素，防止find函数找到的s是原来的那两个

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string str=s+s;
        str.erase(str.begin());
        str.erase(str.end()-1);
        if(str.find(s) != std::string::npos)
            return true;
        else
            return false;
    }
};

另外如果不使用find函数也可以用28.找到字符串第一个匹配项的下标来实现