KMP算法原理--C++//C实现

爱被打了一巴掌 2021-11-23 08:58 287阅读 0赞

# 1 . 背景 定义 #

KMP 用在在一个主文本字符串S内查找一个词W的出现位置

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用暴力算法匹配字符串过程中，我们会把T\[0\] 跟 W\[0\] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T\[1\] 跟 W\[0\]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率

KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数计算了模式串的内部匹配信息。KMP算法的[时间复杂度][Link 1]O(m+n)

[暴力求解与KMP算法内容，不再详述，有很多介绍的][KMP]

下面只讲最难理解的next数组

# 2. 求解 next 数组（核心算法） #

假设 模式串为 abaab，目标找到***每个字符***的**最长公共子序列**

人工计算思路 ,一眼望去最长的公共列是 ab  a  ab    长度为2

算法计算思路 ，从第一个字符 a  向后找，查看有无重复的字符，分别找到了 第三个字符 a 第四个字符 a。

所以存在两种情况，1） 第一个字符及其后面的字符 和 第三个字符及其后面的字符匹配，a\* \* = a \#\#

2） 第一个字符及其后面的字符 和 第四个字符及其后面的字符匹配，a\* \* = a % %

针对第一种情况，再查看第四个字符 a 是否和第二字符 b 相等，相等则 继续查看 第五个字符和 第三个字符 是否匹配。结果是不相等，连续匹配失败，ab 无法和 aa 匹配，aa  ab不是公共子序列。 排除第一种可能

第二种情况，再查看第五个字符 b 是否和第二字符 b 相等, 相等，继续查看，发现到串尾了，结束查找。得到 abaab 最长公共子序列 ab

分解成如下步骤：

0  a  没有公共子序列

0  a b

1 a b a  公共子序列为a 长度是1

1 a b a a

2 a  b a a b  公共子序列为ab 长度是2

程序实现原理，有点类似暴力求解，**注意是模式串远比主串的长度小**，所以暴力求解的时间复杂度仍然低，对模式串的暴力求解得到模式串内部匹配信息，总比对主串暴力求局部匹配情况要优。

初始 i 指向 b; j 指向 a 此时 next \[b\] =0 --------ab 公共子序列长度为0

发现 str \[j\] != str \[i\] ---------从第二个字符开始向后找与第一个字符相等的

没找到，此时 i++

找到了与第一个字符相等的，即有 str \[j\] = str \[i\]

此时 next 应加1，next \[a\] = 1 -----------aba 公共子序列长度为1，也就是 next \[i\] =1

接下来比较 i 后移一位的字符 与 j 后移一位的字符 ，l是否相等

发现 str \[j\] != str \[i\]，断了之前的匹配，j 需要移回 初始位置。开始新一次的查找，查看 初始字符是否与当前 i  匹配

此时 next \[第四个字符a\] = 1 -----------abaa 公共子序列长度为1，也就是 next \[i\] =1

j 需要**移回的数目 其实就是 最长公共子序列，**找公共子序列的过程就是家到学校，移回的过程就是学校到家，前者是去后者是回

发现 str \[j\] = str \[i\] ，找到与第一个字符 a 匹配的第4个字符，继续查看 i → 与 j→ 是否连续匹配

发现匹配，此时 next 应加1，next \[第五个字符b\] = 2 -----------abaab 公共子序列长度为2，也就是 next \[i\] =2

继续查看，后续字母是否匹配，i++ 发现到末尾，则跳出循环查找

# 3. 程序设计 #

void get_next(string s1, int next[]){
        int len = s1.size();
        next[0] = 0;
        int i=1;
        int j=0;
        while(i<len){    //i 到末尾，跳出查询
            if(s1[i] == s1[j]){   // 匹配了，尝试后续字母是否匹配
                next[i] = j+1;
                i++;
                j++;
            }else{     // 三种可能：i头部j头部没匹配；j不在头部，匹配到一半，后面匹配不上，断了匹配；i头部j头部匹配上
                while(j>0 && s1[i]!=s1[j]){  //断了匹配，j移回头部
                    j = next[j-1];
                }
                if(s1[i] == s1[j]){  // 头部匹配上
                    next[i] = j+1;
                    i++;
                    j++;
                }else if(j == 0 && s1[i] != s1[j]){   
               // 初始化查找，将第二个字符 i 和 第一个字符 j 比较
                    next[i] = 0;
                    i++;
                }
            }
        }
     
    }

程序改进，最长公共子序列长度等于 j 移动的步数，那么将 next \[0\] = -1，则有最长公共子序列长度等于 j 所在位置的下标，因此上述代码C++可简写成

void getNext(const string &substr, vector<int> &next)
    {
        next.clear();
        next.resize(substr.size());
        int j = -1;
        next[0] = -1;
    // i 指向字符串 当前字母
        for(int i = 1; i < substr.size(); ++i)  // 末尾，跳出查找
        {
            while(j > -1 && substr[j + 1] != substr[i])  //断了匹配，j移回头部
                j = next[j];
            if(substr[j + 1] == substr[i])  //匹配上，继续查看后续是否匹配
                ++j;
            next[i] = j;  //最长公共子序列长度等于j所在位置的下标
        }
    }

# 4. C++ KMP #

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    void getNext(const string &substr, vector<int> &next)
    {
        next.clear();  //清内存流
        next.resize(substr.size());
        int j = -1;
        next[0] = -1;
        for(int i = 1; i < substr.size(); ++i)
        {
            while(j > -1 && substr[j + 1] != substr[i])   //就地匹配，写成 while 技巧
                j = next[j];
            if(substr[j + 1] == substr[i])
                ++j;
            next[i] = j;
        }
    }
    //传引用比传指针和变量名更安全
    void kmp(const string &str, const string &substr, vector<int> &next)  
    {
        int cnt = 0;
        getNext(substr, next);
        int j = -1;
        for(int i = 0; i < str.size(); ++i)
        {
            while(j > -1 && substr[j + 1] != str[i])  //技巧
                j = next[j];
            if(substr[j + 1] == str[i])
                ++j;
            if(j == substr.size() - 1)
            {
                cout << "find in position" << i << endl;
                ++cnt;
                j = next[j];
            }
        }
        if(cnt == 0)
            cout << "not find" << endl;
    }
    int main()
    {
        string str, substr;
        cin >> str >> substr;
        vector<int> next;
        kmp(str, substr, next);
        return 0;
    }

### C++封装 ###

#include <iostream> 
    #include <vector>
    #include <string>
    using namespace std;
    
    class kmp{    
    private:
       string str1,str2;
       vector<int> next;
    public:
    //构造函数
       kmp(string s1,string s2,vector<int> n){
    	   this->str1=s1; 
    	   this->str2=s2;  
    	   this->next=n;
       }
    //析构函数
       ~kmp(){ 
        cout<<"释放内存"<<endl; 
       }
       void getnext(const string &str2,vector<int> &next); 
       int pattern(const string &str1,const string &str2,vector<int> &next); 
    };   
    void kmp::getnext(const string &str2,vector<int> &next) 
    {
    	next.clear();
        next.resize(str2.size());
        int j = -1;
        next[0] = -1;
        for(int i = 1; i < str2.size(); ++i)
        {
            while(j > -1 && str2[j + 1] != str2[i])
                j = next[j];
            if(str2[j + 1] == str1[i])
                ++j;
            next[i] = j;
        }
    }
    
    int kmp::pattern(const string &str1, const string &str2, vector<int> &next)
    {
        int cnt = 0;
        this->getnext(str2,next);   
        int j = -1;
        for(int i = 0; i < str1.size(); ++i)
        {
            while(j > -1 && str2[j + 1] != str1[i])
                j = next[j];
            if(str2[j + 1] == str1[i])
                ++j;
            if(j == str2.size() - 1)
            {
                cout << "find in position" << i << endl;
                ++cnt;
                j = next[j];
            }
        }
        if(cnt == 0)
            cout << "not find" << endl;
        return cnt;    
    }
    int main()
    {
      string str,substr;  
      vector<int> next;  
      int cal;
      kmp p(str,substr,next); 
      cout<<"输入两个字符串"<<endl; 
      cin>>str>>substr;
      cal=p.pattern(str,substr,next); 
      cout<<"匹配结果"<<cal;
      return 0; 
    }

[Link 1]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6
[KMP]: https://www.cnblogs.com/yjiyjige/p/3263858.html