[8]-代码随想录算法训练营-day9-字符串-part2-526互联

代码随想录算法训练营第九天|字符串-part2

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

题目
- https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
思路
- 暴力for循环
刷随想录后想法
- KMP模式匹配算法
实现困难
- KMP算法理解

实现代码

class Solution {
public:
     void getNext(int *next, string &t){
         //前缀表减一表示法
         int i;
         int j = -1;
         next[0] = -1;
         for (i = 1; i < t.size(); i++){
             //前后缀不一致
             while (t[i] != t[j + 1] && j >= 0){
                 j = next[j];
             }
             //前后缀一致
             if (t[i] == t[j + 1]){
                 j++;
             }
             next[i] = j;
         }
     }
    int strStr(string haystack, string needle) {
        int i;
        int j = -1;
        int next[needle.size()];
        getNext(next, needle);
        //kmp
        for (i = 0; i < haystack.size(); i++){
            //文本串和模式串匹配不一致
            while (haystack[i] != needle[j + 1] && j >= 0){
                j = next[j];
            }
            //如果匹配一致
            if (haystack[i] == needle[j + 1]){
                j++;
            }
            //完成匹配了
            if (j == needle.size() - 1){
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

学习收获
- 理解掌握KMP算法
- 能够熟练编写KMP算法代码

2.Leecode 459. 重复的子字符串

题目

https://leetcode.cn/problems/repeated-substring-pattern/

思路

借用前缀表

如果能够用重复子串表示，以abcabcabcabc为例，则其前缀表应该为

-1 -1 -1 0 1 2 3 4 5 6 7 8

可以明显发现，如果能够用重复子串表示，则前缀表中，三个连续-1所代表的就是子串

前缀表-1之后的前缀，从零开始呈现逐一加一的形式

所以计算串的next数组，然后，利用规律进行判断是否可以表示。

刷随想录后想法

前半部分思路正确，后半部分关于规律的运用仍然存在问题。

根据Carl哥提示，可以直接利用next[s.size() - 1] +1，即最后一个字符所对应的最长相等前后缀长度进行判断。

实现困难

规律的运用，关于最终是否的判断
实现代码
class Solution {
public:
     void getNext(int *next, string &t){
         //前缀表减一表示法
         int i;
         int j = -1;
         next[0] = -1;
         for (i = 1; i < t.size(); i++){
             //前后缀不一致
             while (t[i] != t[j + 1] && j >= 0){
                 j = next[j];
             }
             //前后缀一致
             if (t[i] == t[j + 1]){
                 j++;
             }
             next[i] = j;
         }
     }
    bool repeatedSubstringPattern(string s) {
        int len = s.size();
        int next[len];
        //获取next数组
        getNext(next, s);

        //根据next数组，判断是否能够用重复多次构成，len % (len - (next[len - 1] + 1))，如果能够周期性表示，则此部分为0，关于此部分理解看前缀表即可
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0){
            return true;
        }
        return false;
    }
};
学习收获

本题主要就是对KMP算法的运用

其次，对于规律的判断，采用简单的数学计算即可