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

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

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

1. 题目

   • https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

2. 思路

   • 暴力for循环

3. 刷随想录后想法

   • KMP模式匹配算法

4. 实现困难

   • KMP算法理解

5. 实现代码

   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;
       }
   };
   

6. 学习收获

   • 理解掌握KMP算法
   • 能够熟练编写KMP算法代码

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

1. 题目

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

2. 思路

   • 借用前缀表

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

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

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

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

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

3. 刷随想录后想法

   • 前半部分思路正确，后半部分关于规律的运用仍然存在问题。
   • 根据Carl哥提示，可以直接利用next[s.size() - 1] +1，即最后一个字符所对应的最长相等前后缀长度进行判断。

4. 实现困难

   • 规律的运用，关于最终是否的判断

5. 实现代码

   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;
       }
   };
   

6. 学习收获

   • 本题主要就是对KMP算法的运用
   • 其次，对于规律的判断，采用简单的数学计算即可