KMP刷leetcode速通

前言

KMP真厉害，刷题刷到 28.找出字符串中第一个匹配项的下标 和 1668.最大重复子字符串

next 数组用来匹配不上时，前缀 $j$ 可以快速回退到 $next[j-1]$ 的位置。

void getNext(vector<int>& next, const string& s) {
   int j = 0;  // 后缀
   // next[0] = 0;  // next初始化为 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;   // 更新next数组
   }
}

题目

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

模版题， getNext可以重复使用

class Solution {
public:
    void getNext(vector<int>& next, const string& s) {
        int j = 0;  // 后缀
        // next[0] = 0;  // next初始化为 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;   // 更新next数组
        }
    }
    
    int strStr(string haystack, string needle) {
        // needle是子串
        if (haystack.size() == 0 || needle.size() == 0)
            return -1;
        
        vector<int> next(needle.size(), 0);
        // 构建 next 数组
        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 - j + 1;
        }
        return -1;
    }
};

1668 最大重复子字符串

KMP + 动态规划，很难想象这是 简单 题

class Solution {
public:
    void getNext(vector<int>& next, string s) {
        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;
        }
    }

    int maxRepeating(string sequence, string word) {
        int n = sequence.size(), m = word.size();
        if (n < m)
            return 0;
        
        vector<int> next(m, 0);
        getNext(next, word);

        // 动态规划 dp[i]表示 sequence[0..i]最多有dp[i]个word
        vector<int> dp(n, 0); 
        int j = 0;
        for (int i = 0; i < sequence.size(); i++) {
            while(j > 0 && sequence[i] != word[j])
                j = next[j - 1];
            if (sequence[i] == word[j])
                j++;
                
            if (j == m) {  // 匹配上了开始 dp 操作
                if (i >= m)
                    dp[i] = dp[i - m] + 1;
                else
                    dp[i] = 1;
            }
        }

        int maxVal = 0;
        for (int val: dp)
            maxVal = max(maxVal, val);
        return maxVal;
    }
};