day9

1、KMP算法

1. KMP的作用：KMP用于字符串匹配

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

3. 前缀表

   1. 什么是前缀表？

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

   2. 前缀表的作用？

      前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。（要在文本串中查找是否出现过一个模式串）

   3. 为什么可以使用前缀表可以回退到重新匹配的位置？

      因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

4. 前缀表与next数组

   1. 前缀表 ==》 next数组
   2. 前缀表统一减一 ==》 next数组
   3. 前缀表右移一位，初始位置为-1 ==》next数组

5. 使用next数组进行匹配

6. 时间复杂度

   1. 其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
   2. 暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

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

1. 代码实现

   class Solution {
       public int strStr(String haystack, String needle) {
           if(needle.length() == 0){
               return 0;
           }
   
           int[] next = new int[needle.length()];
           getNext(next, needle);
   
           int j=0; // 因为next数组里记录的起始位置为0
           for(int i=0;i<haystack.length();i++){
               while(j>0 && needle.charAt(j) != haystack.charAt(i)){// 不匹配
                   j = next[j-1];// j 寻找之前匹配的位置
               }
               if(needle.charAt(j)==haystack.charAt(i)){// 匹配，j和i同时向后移动
                   j++;// i的增加在for循环里
               }
               if(j==needle.length()){// 文本串s里出现了模式串t
                   return i-needle.length()+1;
               }
           }
   
           return -1;
   
       }
   
       //前缀表作为next数组
       public void getNext(int[] next, String s){
           int j = 0; //j指向前缀末尾，初始化为0
           next[0] = 0; //当字符串长度为1时，相同前后缀的长度为0
           for(int i=1; i<s.length(); i++){//i指向后缀末尾
               while(j>0 && s.charAt(j) != s.charAt(i)){
                   j = next[j-1]; //循环不变量：每次匹配不成功时，从当前位置的上一位在next数组中找回退位置
               }
               if(s.charAt(j)==s.charAt(i)){
                   j++;
               }
               next[i]=j; // 将j（前缀的长度）赋给next[i]  
           }
       }
   }
   

3、leetcode459 重复的子字符串

1. 代码实现

   class Solution {
       public boolean repeatedSubstringPattern(String s) {
           if(s.length()==0){
               return false;
           }
           int[] next = new int[s.length()];
           getNext(next,s);
           int len = s.length();
           if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
               return true;
           }
           return false;
       }
   
       //前缀表作为next数组
       public void getNext(int[] next, String s){
           int j = 0;
           next[0] = 0;
           for(int i=1; i<s.length(); i++){
               while(j>0 && s.charAt(j)!=s.charAt(i)){
                   j=next[j-1];
               }
               if(s.charAt(j)==s.charAt(i)){
                   j++;
               }
               next[i]=j;
           }
       }
   }