刷题总结——字符串KMP算法分析与应用

本文最后更新于：2021年7月28日 下午

刷题总结——字符串的KMP算法分析与应用

概述

  • KMP的经典思想就是：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
    • 如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任
  • next数组：前缀表（prefix table）
    • 前缀表是用来回退的，它记录了模式串(与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
    • 记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀
  • 最长相等前后缀
    • 前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串
    • 后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串
    • 前缀表要求的就是相同前后缀的长度

如何构造前缀表和next数组

  • 前缀表中记录了模式串中每个位置从 [0,位置] 的最长相等前后缀的长度

    • 前缀表的长度等于模式串

  • 当在 模式表i 处发生不匹配时，只需找到前缀表中i-1的位置处的值，即可知道下次匹配从模式表[前缀表[i-1]]处开始

  • 为了简便，通常会将前缀表向右移动并赋初值为-1，得到next数组,这样下次匹配就是模式表[next[i]]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /*构造nextu
    1. 初始化
    2. 处理前后缀不同的情况
    3. 处理前后缀相同的情况
    整个算法有点动态规划的味道，在前一段完成的基础上，获得下一段的情况
    */
    void getNext(int* next, const string& s) {
    	next[0] = -1;	//先给next[0]赋初值,必定是-1
        int j = 0;		
    	int k=-1;		//记录s[0]-s[j-1]最长相等前缀的后一个位置
       	while(j<s.length()-1){		//因为我们是使用右移的next数字，所以循环的j实际上是给j+1赋值
        	if(k==-1||s[j]==s[k]){		//这里加k==-1这个条件，实际上也是一个给next[1]赋初值的条件，因为s[1]不匹配的话，只能用s[0]l来匹配，
        //如果s[j+1]不匹配,考虑0-j的字符串,当s[k]==s[j]时,0-j字符串的k应该是k+1，所以s[j+1]=k+1（之后为了下次循环，k，j也要往前移动一位）
                j++;k++;
             	next[j]=k;	
            }else{						
            //如果s[j+1]不匹配时，考虑0-j的字符串，当s[j]!=s[k]，0-j的最长相等前缀位置不是k(因为k是0-j-1的)，所以要更新这次的k。因为k是0-j-1的最长相等前缀的后一个位置，所以s[j]!=s[k]最长前缀只可能在0-k-1中出现，那么next[k]就应该是下一个去匹配的位置，进入下一次循环判断直到有s[k]==s[j],那么此时的k就是0-j处的最长前缀的后一个位置
                k=next[k];
            }    
        }
    }

题目练习

在一个串中查找是否出现过另一个串

  • 28.Implement strStr()

    • next数组可以优化

      1
      next[j]=s[j]!=s[k]?k:next[k]//next数组优化，避免s[j+1]发生不匹配时，下一个s[next[j+1]]==s[j+1]继续不匹配，需要继续往下匹配

扩展阅读