KMP 算法原理，以及算法的c++示例代码

你的名字 2023-10-15 22:04 11阅读 0赞

### 引言 ###

KMP 算法，即 Knuth-Morris-Pratt 算法，是一种用于字符串匹配的经典算法。与朴素的字符串匹配算法相比，KMP 算法具有更高的效率，特别是在处理大型文本时。本文将介绍 KMP 算法的原理，并提供 C++示例代码来演示如何实现它。

### KMP 算法原理 ###

KMP 算法的核心思想是避免在文本串中进行不必要的比较。在传统的朴素匹配算法中，每当我们在文本中找到不匹配的字符时，我们会将子串向右移动一个位置，并重新开始比较。这种方法的问题是，我们可能会多次比较相同的字符。

KMP 算法通过构建部分匹配表（也称为失配函数）来解决这个问题，以在不匹配时跳过尽可能多的字符。部分匹配表告诉我们在不匹配时应该将子串移动到的位置，而不是每次都向右移动一个位置。这样，我们可以避免不必要的比较，提高了算法的效率。

下面是 KMP 算法的主要步骤：

1.  构建部分匹配表：首先，我们需要计算出子串的部分匹配表。这个表告诉我们每个位置上的最长匹配前缀长度。部分匹配表的构建是 KMP 算法的关键步骤。
2.  在文本中搜索匹配：然后，我们在文本串中遍历字符，同时在子串中遍历字符，使用部分匹配表来决定如何移动子串。
3.  部分匹配表的应用：当发生不匹配时，部分匹配表告诉我们应该将子串移动多远，而不是重新开始比较。

下面，让我们逐步讲解 KMP 算法的实现。

### KMP 算法的 C++实现 ###

#### 步骤 1：构建部分匹配表 ####

首先，让我们来实现部分匹配表的构建。部分匹配表告诉我们每个位置上的最长匹配前缀长度。

#include <iostream>
    #include <vector>
    #include <string>
    
    std::vector<int> buildPartialMatchTable(const std::string& pattern) {
        
        int m = pattern.size();
        std::vector<int> table(m, 0);  // 初始化部分匹配表
    
        int len = 0;  // 当前匹配的前缀长度
        int i = 1;
    
        while (i < m) {
        
            if (pattern[i] == pattern[len]) {
        
                len++;
                table[i] = len;
                i++;
            } else {
        
                if (len != 0) {
        
                    len = table[len - 1];
                } else {
        
                    table[i] = 0;
                    i++;
                }
            }
        }
    
        return table;
    }

#### 步骤 2：在文本中搜索匹配 ####

接下来，我们将实现 KMP 算法的主要搜索部分，即在文本中搜索匹配子串。

std::vector<int> KMPSearch(const std::string& text, const std::string& pattern) {
        
        int n = text.size();
        int m = pattern.size();
        std::vector<int> result;
    
        std::vector<int> lps = buildPartialMatchTable(pattern);
        int i = 0;  // 文本指针
        int j = 0;  // 子串指针
    
        while (i < n) {
        
            if (pattern[j] == text[i]) {
        
                i++;
                j++;
            }
    
            if (j == m) {
        
                result.push_back(i - j);
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
        
                if (j != 0) {
        
                    j = lps[j - 1];
                } else {
        
                    i++;
                }
            }
        }
    
        return result;
    }

#### 步骤 3：使用 KMP 算法 ####

现在，我们可以使用 KMP 算法在文本中搜索匹配的子串了。

int main() {
        
        std::string text = "ABABDABACDABABCABAB";
        std::string pattern = "ABABCABAB";
        std::vector<int> matches = KMPSearch(text, pattern);
    
        if (matches.empty()) {
        
            std::cout << "未找到匹配的子串。" << std::endl;
        } else {
        
            std::cout << "在以下位置找到匹配的子串：" << std::endl;
            for (int match : matches) {
        
                std::cout << match << " ";
            }
            std::cout << std::endl;
        }
    
        return 0;
    }

### 结论 ###

KMP 算法是一种高效的字符串匹配算法，它通过构建部分匹配表来避免不必要的字符比较，从而提高了搜索效率。在 C++中实现 KMP 算法需要以下步骤：构建部分匹配表，然后在文本中搜索匹配的子串。希望本文能帮助你理解 KMP 算法的原理和实现方式，并在需要时能够成功应用它。