代码随想录算法训练营第九天 | 28、找出字符串中第一个匹配项的下标、459. 重复的子字符串

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

题目链接：28、找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

文章讲解/视频讲解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html

思路

这道题是KMP的经典题目。KMP的思想是：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

这里摘录一下卡哥教程中的内容。

什么是KMP

说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。

因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP。

KMP有什么用

KMP主要应用在字符串匹配上。

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

什么是前缀表

KMP代码中的next数组就是一个前缀表。

前缀表有什么作用呢？

前缀表是用来回退的，它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配。

前缀表：记录下标i之前（包括i）的字符串，有多大长度的相同前缀后缀。

最长公共前后缀

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

如何计算前缀表

对数组中的每一个位置遍历，计算当前位置的前缀和后缀中，最大相等长度，填入前缀表。一个示例如下：

在这里插入图片描述

前缀表如何使用

找到不匹配的位置，此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢，因为要找前面字符串的最长相同的前缀和后缀。

如果前一个字符的前缀表的数值是2，那么把下标移动到下标2的位置继续匹配。

直到找到了和模式串匹配的子串为止。

解题

解这道题分为两步，构造next数组，然后利用next数组进行匹配。

构造next数组

构造next数组其实就是计算模式串s，前缀表的过程，主要有如下三步：

1.初始化

定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。j初始化为0。

2.处理前后缀不相同的情况

因为i指向的是后缀末尾位置，遍历时，i从1开始，如果s[i]与s[j]不相同，即遇到了前后缀不相同的情况，就要向前回退，令j = next[j - 1]。

3.处理前后缀相同的情况

如果s[i]与s[j]相同，则说明遇到了相同的前后缀，那么这时可以将j后移，j++，再将j赋值给next数组，记录在i这个位置，前后缀相等的最大长度。

这一步的过程，我的理解是模式串在进行自匹配。

使用next数组来做匹配

在文本串s里找是否出现过模式串t。

定义两个下标i和j，下标j指向模式串的起始位置，i指向文本串当前匹配的末尾位置。j初始化为0。

i从0开始遍历文本串，令s[i]与t[j]做比较，如果不相同，j就要从next数组中寻找下一个匹配的位置，令j = next[j]，如果相同，则i和j同时后移。

如何判断文本串s里出现了模式串t？如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s的某个子串了。

C++实现

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

    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        if(needle.size() > haystack.size()) return -1;

        vector<int> next = getNext(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. 重复的子字符串

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

文章讲解/视频讲解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

思路

可以按照KMP的思路，对该字符串s求解其前缀表，即next数组。

然后在前缀表中寻找值连续的第一个下标i，此时说明i及之后的字符串元素都是连续自匹配的，i的值即为模式子串的长度pattenLen。

判断s.size() % pattenLen是否等于0，如果等于0，则说明该字符串可由子串重复构成。注意判断pattenLen的值既不能等于0也不能等于s.size()。

例如：对于字符串s = “babbabbabbabbab”，其next数组为：

[0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

找到值连续的第一个下标i为3，字符串的长为15，15 % 3 = 0，说明可由子串构成，i的大小即为模式子串的长度。

下标i可由next.size() - next[next.size() - 1]得到。

C++实现

class Solution {
public:

    vector<int> getNext(const string& s){
        vector<int> next(s.size(), 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;
        }
        return next;
    }

    bool repeatedSubstringPattern(string s) {
        if(s.size() == 1) return false;
        vector<int> next = getNext(s);
        int pattenLen = next.size() - next[next.size() - 1];

        return (s.size() % pattenLen == 0) && pattenLen != 0 && pattenLen != next.size();
    }
};