KMP字符串匹配算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了KMP字符串匹配算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1548字，纯文字阅读大概需要3分钟。

内容图文

1. KMP算法用途

KMP算法用于解决主字符串和模式字符串匹配的问题。如果完成匹配，返回模式字符串在主字符串匹配的初始索引。如果不匹配，返回-1。

2. PMT(Partial Match Table)：部分匹配表（模式字符串）

部分匹配表是KMP算法的核心，定义：前缀集合和后缀集合交集中最长元素的长度。

前缀集合：如果字符串M = A + S，A和S非空，则A是M的一个前缀，所有的前缀组成前缀集合。

后缀集合：如果字符串M = A + S，A和S非空，则S是M的一个后缀，所有的后缀组成后缀集合。

图中表示了Index = 10时，PMT = 4的计算过程，前缀字符串abab与后缀字符串abab匹配。

如果主字符串是T，匹配字符串是P，T[ i ] != P[ j ]时，此时可以通过右移匹配字符串PMT[ j - 1 ]个单位来解决，即令 j = PMT[ j - 1]

为了简化计算，引入next数组记录 j 索引处 PMT[ j - 1 ]的数值。

如果T[ i ] = P[ j ]，则i++, j++，表示目前匹配

如果T[ i ] != P[ j ]

　　如果 j == -1，则需要 i++, j++，j++ 表示P 从0开始匹配，i++表示当前不匹配，从下一个位置开始匹配。

　　如果 j != -1，则从后缀字符串与前缀字符串已经匹配，令 j = next[j]即可。

3. KMP算法实现

循环结束，当 j == strlen(p)时，表示完全匹配，此时返回 i - j 表示匹配的起始位置。

int KMP(char * t, char * p) 
{
    int i = 0; 
    int j = 0;

    while (i < strlen(t) && j < strlen(p))
    {
        if (j == -1 || t[i] == p[j]) 
        {
            i++;
                   j++;
        }
         else 
                   j = next[j];
        }

    if (j == strlen(p))
       return i - j;
    else 
       return -1;
}

4. PMT, next实现过程

通过移动与自身字符串匹配求next：

注意:如果不匹配，j 的值应该设为：next[j]，继续向下匹配，直到为 j = -1 为止再从0开始匹配，下图说明了原因。

 

代码实现：

void getNext(char * p, int * next)
{
    next[0] = -1;
    int i = 0, j = -1;

    while (i < strlen(p))
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }    
        else
            j = next[j];
    }
}

内容总结

以上是互联网集市为您收集整理的KMP字符串匹配算法全部内容，希望文章能够帮你解决KMP字符串匹配算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---