【数据结构算法】KMP算法（字符串匹配算法）

系统管理员 2022-05-21 05:49 242阅读 0赞

### BF算法（Brute Force） ###

朴素的字符串模式匹配算法，核心思想是：有两个字符串S和T，长度为N和M。首先S\[1\]和T\[1\]比较，若相等，则再比较S\[2\]和T\[2\]，一直匹配到T\[M\]为止，若S\[1\]和T\[1\]不相等，则T向右移动一个字符的位置，再依次进行比较。  
![这里写图片描述][70]  
![这里写图片描述][70 1]  
![这里写图片描述][70 2]

### KMP算法 ###

由于上述BF算法的匹配方式效率不高，所以提出了KMP算法。  
**核心思想**：提出了next矩阵，用来存储当失配时回溯法所回溯到的位置。所以我们要有一个构建模式匹配串的函数，称之为get\_next,用来得到对应的模式匹配串的next矩阵，所以这个next矩阵的构建和目标串没有任何关系，只取决于模式匹配串。

j = 0;    //j表示的是前缀  
    i = 1;    //i表示的是后缀
    next[1] = 0;
    while(i<T[0])
    {
        if(0 == j || T[i] == T[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j = next[j]; //这一步就是当不匹配的时候回溯到相应的位置的操作
        }
    }

### 调用匹配代码 ###

int index_KMP(String S, String T, int pos)
    {
        int i = pos;//表示从哪个位置开始进行匹配
        int j = 1;
        int next[255];
    
        get_next(T, next);//只需要传入模式匹配串T和next的地址（因为需要修改next矩阵）
        while(i<=S[0]  && j<==T[0])
        {
            if(S[i] == T[i])
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];
            }
        }
    
        if(j>T[0])
        {
            return i-T[0];
        }
        else
        {
            return 0;
        }
    }

### 优化KMP算法 ###

后来有人发现，KMP算法的缺陷在于，当我们的主串S=”aaaabcde”,子串T = “aaaaax”，这样的话next矩阵就会是012345，但这会使得匹配效率变得不那么高，因此用下面优化部分的代码段可以提高匹配效率。

#include<stdio.h>
    
    typedef char* String;
    
    void get_next(String T, int *next)
    {
        int i = 1;
        int j = 0;
        next[1] = 0;
    
        while(i<T[0])
        {
            if(0 == j || T[i] == T[j])
            {
                i++;
                j++;
                //这一段优化是用来优化上述情况的
                if(T[i]!=T[j])
                {
                    next[i]=j;
                }
                else
                {
                    next[i] = next[j];//
                }
            }
            else
            {
                j = next[j];
            }
        }
    }

[70]: /images/20220521/8b894642d5c944e3af731f40e0d47ad1.png
[70 1]: /images/20220521/75076f087b2b4acaadf415374410123b.png
[70 2]: /images/20220521/a9fc751979c04386b07eb08aa7a5d972.png