【AcWing14】【LeetCode】KMP算法-28/796/214/459

这个博主的图解原理非常好！

https://leetcode.cn/problems/shortest-palindrome/solution/tu-jie-kmpsuan-fa-by-yangbingjie/

这个算法一开始看还真看不明白，收藏这个博主的详细讲解。
（算法）通俗易懂的字符串匹配KMP算法及求next值算法

代码模板

#include 
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char s[M], p[N];
int m, n, ne[N];

int main()
{
    //字符从第一个开始读入，你看后面循环也是，i=1，j+1=1，看个人习惯，无所谓
    cin >> n >> p+1;
    cin >> m >> s+1;
    
    for(int i=2,j=0;i<=n;i++)
    {
    	//与后搜索理解类似
        while(j && p[i] != p[j+1]) j = ne[j];
        if(p[i] == p[j+1]) j++;
        ne[i] = j;
    }
    
    //每次比的都是i和j+1
    for(int i=1,j=0;i<=m;i++)
    {
    	//每次没匹配并且还没退到最开始就往回退
        while(j && s[i] != p[j+1]) j = ne[j];
        //匹配了，就往下走一位
        if(s[i] == p[j+1]) j++;
        if(j == n)
        {
            //题意从0开始算下标
            cout << i - n << " ";
            //匹配成功，退一步接着往后看
            j = ne[j];
        }
    }
    return 0;
}
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

LeetCode 28. 实现strStr()

匹配原理：
1.求str1[i+1]对应的next值，即求str1[0]_{str1[i]这段的最大公共前后缀。求str1[0]}str1[i]的最大公共前后缀，需要遍历str1[0]~str[i - 1]中所有的公共前后缀，直到新元素和前缀的下一位相同即为匹配成功，新的公共最长前后缀的长度即为当前遍历的公共前后缀长度+1，next[i+1]=新的长度+1(next值需要额外加1，原因见下文)。如果遍历完所有的公共前后缀都没有满足条件，则next[i+1]=1， 意味着该位匹配失败得直接从头再来匹配了。（我们将第一位的next值定义为0，意味着如果遍历到了这里，就说明已经遍历完了所有前后缀了，也正是因为如此，我们要将其他元素的next值定义为最长公共前后缀的值+1，其实就是为了区分这个起始的0）

void next(string& str1, vector<int> &next){
    int length = str1.size();
    next.resize(length + 1);
    next[0] = -1; 
    next[1] = 0;
    int i = 1;
    int j = 0;
    while (i < length)
    {
        if(j == 0 || str1[i-1] == str1[j-1]){//当所有公共前后缀都匹配不上或者匹配成功
            next[++i] = ++j;                 //更新next
        }else{
            j = next[j];//遍历下一个可能的公共前后缀
        }
    }
}

作者：hei-xiao-chang-pian
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/kmp-by-hei-xiao-chang-pian-o6j9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

代码随想录的题解比acwing的好

链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/dai-ma-sui-xiang-lu-kmpsuan-fa-xiang-jie-mfbs/

class Solution {
public:
    void getNext(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) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        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;
    }
};

作者：carlsun-2

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

LeetCode 796.旋转字符串

class Solution {
public:
    void getNext(string& p, vector<int>& next) {
        int pLen = p.size();
        next.resize(pLen, -1);
        int k = -1, j = 0;
        while (j < pLen - 1) {
            if (k == -1 || p[k] == p[j]) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
    }
    bool rotateString(string A, string B) {
        if (A.size() != B.size()) return false;
        A += A;
        int ALen = A.size();
        int BLen = B.size();
        vector<int> next;
        getNext(B, next);
        int i = 0, j = 0;
        while (i < ALen && j < BLen) {
            if (j == -1 || A[i] == B[j]) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        return j == BLen ? true : false;
    }
};
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

LeetCode 214. 最短回文串

class Solution {
public:
    int commpute_next(string pattern){
        vector<int>next(pattern.size() + 1, 0);
        next[0] = -1;
        next[1] = 0; // 长度为1的字符串没有前后缀
        int i = 2; // i表示next数组的索引
        int k = 0; // 指针指向pattern的位置
        while (i < next.size()) {
            // 如果当前字符匹配成功
            if (pattern[i - 1] == pattern[k]) { // pattern索引比next索引小1
                next[i] = k + 1;
                k = next[i];
                ++i;
            // 如果指针已经指向pattern[0]却还没有匹配成功
            } else if (k == 0){
                next[i] = 0;
                ++i;
            } else{
                k = next[k]; //可以利用已匹配成功的信息，让指针不进行回退，查找next数组
            }
        }
        return next[next.size() - 1]; // 只需要返回最后一个值
    }

    string shortestPalindrome(string s) {
        if(s == ""){
            return "";
        }
        string reverse_str(s.rbegin(), s.rend());
        string pattern = s + '#' + reverse_str;
        int max_len = commpute_next(pattern);
        return reverse_str.substr(0, reverse_str.size() - max_len) + s;
    }
};

作者：yangbingjie
链接：https://leetcode.cn/problems/shortest-palindrome/solution/tu-jie-kmpsuan-fa-by-yangbingjie/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

LeetCode 459. 重复的子字符串-要再思考一下

代码随想录的题解要配上以下kmp详解
https://www.bilibili.com/video/BV1cg41127fw/

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.matrix67.com/blog/archives/115

和这个
https://blank.blog.csdn.net/article/details/80979293

S=S1S2S3
如果最长的公共前后缀是S1S2， 那么重叠的一定是重复的子串，这里一定要理解。反复揣摩什么是公共前后缀。

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 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;
        }
    }
    bool repeatedSubstringPattern (string s) {
        if (s.size() == 0) {
            return false;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

作者：carlsun-2
链接：https://leetcode.cn/problems/repeated-substring-pattern/solution/by-carlsun-2-g3iz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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