Klausur Algorithmen und Datenstrukturen
原创2024年2月3日大约 2 分钟...约 584 字
KMP-Algorithmus
(a) Bestimmen Sie mit Hilfe des KMP-Algorithmus die Verschiebetabelle für das folgende Pattern und tragen Sie es in die Tabelle ein.
KMP 算法，全称 Knuth-Morris-Pratt 算法，是一种用于字符串搜索的高效算法。它的主要目的是在一个文本字符串中查找一个词（称为模式串）的出现，其核心思想是当出现不匹配时，能够利用已经匹配的部分信息避免从文本串的起始位置重新开始搜索。
在传统的字符串搜索算法中，当模式串与主文本串不匹配时，你通常会将模式串向右移动一位。然而，KMP 算法通过预处理模式串并构建一个所谓的“部分匹配”表（也称为“失配表”或“前缀函数”），从而实现更有效的搜索。这个表包含了在模式串中对自身进行匹配时，每个位置上的最长公共前后缀的长度。有了这个信息，当不匹配发生时，就可以直接将模式串移动到前缀的下一个字符，而不是完全回退到文本串中的下一个字符。
KMP 算法的步骤大致如下：
预处理模式串：计算部分匹配表，这个表指明了当模式串在某位置不匹配时，模式串应该回退到哪个位置。这一步是KMP算法的核心，能够避免在文本串中的不必要比较。
搜索过程：使用部分匹配表进行搜索。开始时模式串与文本串对齐在第一个字符。在搜索过程中，当模式串的某个字符与文本串不匹配时，可以利用部分匹配表中的信息来决定下一步的移动。这意味着模式串可以向右滑动超过一个字符。
KMP 算法的效率之所以高，是因为它保证了模式串在每次不匹配发生时，都能尽可能地向右移动最远距离，这样就避免了对文本串的重复扫描，从而提高了搜索效率。