数据结构复习4

第四章 串

一些面试题

12. 介绍一下KMP算法。★★★

       KMP算法是一种高效的字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。KMP算法通过利用模式串自身的信息，在匹配过程中避免不必要的回溯，从而提高匹配效率。

       KMP算法的核心思想是使用一个部分匹配表，也称为next数组，来记录模式串中每个位置的最长公共前后缀的长度。这样，在匹配失败时，可以根据部分匹配表的信息，将模式串向右移动尽可能少的步数。

       KMP算法的时间复杂度O(n+m)，朴素算法的时间复杂度O(n*m)，n和m是两个串的长度。

-------------------------------------------------------------------------------------------------------------------------

       KMP算法的具体步骤如下：

预处理next数组：对于模式串，遍历每个位置，计算该位置之前子串的最长公共前后缀的长度，并保存到next数组中。
匹配过程：从文本串的起始位置开始，用两个指针分别指向文本串和模式串的当前位置，逐个字符进行比较。
       如果当前字符匹配成功，则两个指针同时向后移动一位。

       如果当前字符匹配失败：

       根据next数组中的信息，将模式串向右移动尽可能少的步数。根据当前失败位置的部分匹配值，向右移动模式串的指针。

       同时，保持文本串的指针不动，继续与模式串的新位置进行比较。

       如果模式串的指针移到末尾，则表示匹配成功，返回在文本串中的起始位置。如果文本串的指针移到末尾，则表示未找到匹配，返回-1。

--------------------------------------------------------------------------------------------------------------------------

KMP算法简述

KMP算法是在简单模式匹配的基础上对串的模式匹配进行优化。

主要的思路是每趟比较过程中让子串先滑动到一个合适的位置。

当发生不匹配时，不同于简单模式匹配的右移一位，而是移动到适合的位置。

这里所移动的位置依靠与NEXT[]数组，求next[]数组的方法是比较前后缀相同元素。

计算机保研/考研面试题——数据结构与算法篇_计算机保研面试 csdn-CSDN博客

面试考点——数据结构篇_数据结构保研面试重点-CSDN博客