●28. 实现 strStr() ●459.重复的子字符串 ●字符串总结 ●双指针回顾

实现strStr（）

  • KMP算法的核心是前缀表，实际KMP就是为了避免不匹配时重新匹配，使用的技术是最长公共前后缀，因为每次不匹配时，已经扫过了文本串和模式串的后缀，而如果能知道和模式串后缀相等的最长相等前缀是多少，就能保证文本串的后缀（xxxxxaaxxxxx）和模式串的前缀（aaxxxaa）相等，这样这部分相等的就不用匹配了直接从模式串前缀的后一个字符开始匹配,文本串的指针也不用移动。而最长公共前后缀的长度恰好就是从0开始，继续匹配的索引位置（0 + 公共前缀长度 = 公共前缀的下一位下标），这样也就知道了匹配失败之后，应该去哪匹配最合适。
  • 因此前缀表存的就是包括当前元素之前的最长公共前后缀的长度，或者说匹配失败时继续匹配的下标位置，只不过实现时next数组可能-1，右移，如果不动，匹配失败时就找前面一个元素的前缀表（不包括冲突元素），如果右移就找当前元素的前缀表，方便了点。
  • 实现分四步，初始化，处理前后缀不同，处理前后缀相同，更新next前缀表。
  • i是后缀的末尾，j是前缀的末尾，也是最长公共前缀的长度，这点要注意，j兼具前缀结果和匹配的两用。
  • j初始化为0，i初始化为1，next[0] = 0,i遍历更新模式串每一位，j在这一过程中动态维护得到每个i的最长公共前缀的next[i]。
  • 前后缀不同时，找前缀前一位的nextj-1，注意是s[next[j-1]]仍旧可能不匹配,所以要用while不断回退，直到回退到第一个元素或者匹配为止，在这一过程中最长前缀j本身也被维护记录了。整体思路像数学归纳法。
  • 前后缀相同时，j++，同时更新next[i] = j 然后再i++。
  • 匹配时，再重复以上逻辑，此时i是文本串，j是模式串，i，j都从0开始，只不过匹配时不再更新next[i]，字符不匹配，j回退，匹配时j++,当j == 模式串大小时（注意，不是=size-1，j指向的一直是满足匹配时的下一位）。
  • 如果模式串是空串，返回0，认为空串和任意字符串在0匹配 = “” + str。
  • 时间复杂度O(m + n),包括根据模式串构建前缀表和匹配遍历文本串。实际上构建前缀表的逻辑和匹配的逻辑都是一样的，只不过匹配相等时不更新next数组，当j到达模式串长度就匹配成功。
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0)
            return 0;
        //初始化
        int j = 0;
        vector<int> next(needle.size(), 0);
        next[j] = 0;
        //计算needle的前缀表
        for (int i = 1; i < needle.size(); i++) {
            //处理前后缀不同的情况
            while (j > 0 && needle[j] != needle[i]) {
                j = next[j - 1];
            }
            //处理前后缀相同的情况
            if (needle[j] == needle[i]) {
                j++;
            }
            next[i] = j;
        }
        j = 0;
        //匹配
        for (int i = 0; i < haystack.size(); i++) {
            while (j > 0 && needle[j] != haystack[i]) {
                j = next[j - 1];
            }
            if (needle[j] == haystack[i]) {
                j++;
            }
            if (j == needle.size()) return (i - j + 1);
        }
        return -1;
    }
};

重复的子字符串

  • 移动匹配,掐头去尾拼一块，中间还能出现自己那就时可重复的（可重复，顺序不影响，而不可重复如果顺序换了那一定不行），find的实现复杂度类似KMP模板在O(m + n)。

alt

alt

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin());
        t.erase(t.end() - 1);
        if (t.find(s) != std::string::npos) {
            return true;
        }
        return false;
    }
};
  • KMP,对于整个假设重复的个字符串，最长公共前缀和后缀的非公共部分就是最小重复单元(前缀后缀本身定义不包含首字母或者尾字母，所以第一个最小重复结构肯定不在前后缀的相交部分（首字母不匹配）)，如果能整出就满足情况。
  • 实现的时候用数组size整出最小重复单元大小看能除尽不，注意要排除整个子串没有公共前后缀的情况，自己长度除自己也能除尽。
  • 本题的技巧在只考虑符合最小重复字符串的条件，其他条件都不考虑，是个必要条件。
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        //求前缀表next数组
        int j = 0;
        vector<int> next(s.size(), 0);
        for (int i = 1; i < s.size(); i++) {
            while(j > 0 && s[j] != s[i]) {
                j = next[j - 1];
            }
            if (s[j] == s[i]) j++;
            next[i] = j;
        }
        //找出最小重复单元 字符串长度-整个字符串最长公共前后缀长度
        int len = s.size() - (next[s.size() - 1]);
        if (next[s.size() - 1] != 0 && s.size() % len == 0) return true;
        return false;
    }
};

int main() {
    string s;
    cin >> s;
    Solution s1;
    cout << s1.repeatedSubstringPattern(s);
    return 0;
}

字符串总结，

双指针回顾

在344.反转字符串 (opens new window)，我们使用双指针法实现了反转字符串的操作，双指针法在数组，链表和字符串中很常用。

接着在字符串：替换空格 (opens new window)，同样还是使用双指针法在时间复杂度O(n)的情况下完成替换空格。

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

那么针对数组删除操作的问题，其实在27. 移除元素 (opens new window)中就已经提到了使用双指针法进行移除操作。

同样的道理在151.翻转字符串里的单词 (opens new window)中我们使用O(n)的时间复杂度，完成了删除冗余空格。

  • 考虑局部反转再整体反转会起到很牛的效果，比如左旋字符串。

alt

alt