算法:字符串的KMP模式匹配

在朴素的模式匹配算法中,主串的pos值(i)是不断地回溯来完成的(见字符串的基本操作中的Index函数)。而计算机的大仙们发现这种回溯其实可以是不需要的。既然i值不回溯,也就是不可以变小,那么考虑的变化就是子串的pos值(j)了。通过分析发现子串中如果有相等字符,j值的变化就会不相同,也就是说,这个j值的变化跟主串其实没什么关系,关键就取决于子串的结构中是否有重复的问题。

我们把子串各个位置的j值变化定义为一个数组next,那么next的长度就是子串的长度(next[0]空置)。于是可以得到下面的函数定义。

下面摘录一段阮一峰所写关于kmp的文章,增进理解:

因为空格与C 不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABC"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;

  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;

  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

示例代码:(改编自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 30
typedef char String[MAXSIZE + 1]; //以'\0'结尾
/* 生成一个串*/
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '\0';
    return true;
}

int StrLength(String Src)
{
    int i = 0;
    while (Src[i] != '\0')
        i++;
    return i;
}

void StrPrint(String Src)
{
    cout << "Print Str ..." << endl;
    for (int i = 0; Src[i] != '\0'; i++)
        cout << Src[i];
    cout << endl;

}
/* 通过计算返回子串Sub的next数组。 */
void GetNext(String Sub, int *next)
{
    int i = 1;
    int j = 0;
    next[1] = 0;
    while (i < StrLength(Sub))
    {
        if(j == 0 || Sub[i - 1] == Sub[j - 1])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];/* 若字符不相同,则j值回溯 */
    }
}

void GetNextVal(String Sub, int *nextval)
{
    int i = 1;
    int j = 0;
    nextval[1] = 0;
    while (i < StrLength(Sub))
    {
        if(j == 0 || Sub[i - 1] == Sub[j - 1])
        {
            ++i;
            ++j;
            if (Sub[i - 1] != Sub[j - 1]) /* 若当前字符与前缀字符不同 */
                nextval[i] = j;/* 则当前的j为nextval在i位置的值 */
            else
                nextval[i] = nextval[j];/* 如果与前缀字符相同,则将前缀字符的 */
            /* nextval值赋值给nextval在i位置的值 */
        }
        else
            j = nextval[j];
    }
}
/* 返回子串Sub在主串Src中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
int IndexKMP(String Src, String Sub, int pos)
{
    cout << "KMP Index ..." << endl;
    int i = pos - 1;
    int j = 0;
    int next[10];
    int len1 = StrLength(Src);
    int len2 = StrLength(Sub);
    /*GetNext(Sub, next);*/
    GetNextVal(Sub, next);

    while (i < len1 && j < len2)
    {
        /* 两字母相等则继续,与朴素算法增加了j=0判断 */
        if (j == 0 || Src[i -1] == Sub[j -
1])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];/* j退回合适的位置,i值不变 */
        }
    }

    if (j == len2)
        return i - len2 + 1;
    else
        return 0;
}

int main(void)
{
    String Str1, Str2, Str3, Str4;
    StrAssign(Str1, "defewabcabxwfew");
    StrAssign(Str2, "abcabx");
    StrAssign(Str3, "ababaaaba");
    StrAssign(Str4, "htrhdhsgtrhababaaabafwrew");

    int next[10]; //next[0]空置
    GetNext(Str2, next);
    cout << "Get Next array ..," << endl;
    for (int i = 1; i < 7; i++)
        cout << next[i];
    cout << endl;

    GetNext(Str3, next);
    cout << "Get Next array ..," << endl;
    for (int i = 1; i < 10; i++)
        cout << next[i];
    cout << endl;

    GetNextVal(Str3, next);
    cout << "Get NextVal array ..," << endl;
    for (int i = 1; i < 10; i++)
        cout << next[i];
    cout << endl << endl;

    cout << IndexKMP(Str1, Str2, 1) << endl;
    cout << IndexKMP(Str4, Str3, 1) << endl;

    return 0;
}

输出为:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏进击的程序猿

Say No to Loop!

本文会介绍下Eloquent\Collection,这个是什么呢?这是我们平常使用Eloquent中get,all返回的结果集。

9630
来自专栏aCloudDeveloper

LeetCode:151_Reverse Words in a String | 字符串中单词的逆反 | Medium

题目:Reverse Words in a String Given an input string, reverse the string word by w...

22760
来自专栏Golang语言社区

Go语言 枚举和类型

package mainimport "fmt"//1.枚举的使用// 枚举指一系列相关的常量,比如下面关于一个星期中每天的定义。通过上一节的例子,我们// 看...

37280
来自专栏菜鸟前端工程师

JavaScript学习笔记017-数值方法0Math0定时器

8230
来自专栏一个会写诗的程序员的博客

Scala类型推导Scala类型推导

根据Picrce的说法:“类型系统是一个可以根据代码段计算出来的值对它们进行分类,然后通过语法的手段来自动检测程序错误的系统。”

16020
来自专栏函数式编程语言及工具

Scalaz(4)- typeclass:标准类型-Equal,Order,Show,Enum

  Scalaz是由一堆的typeclass组成。每一个typeclass具备自己特殊的功能。用户可以通过随意多态(ad-hoc polymorphism)把这...

19750
来自专栏逍遥剑客的游戏开发

纹理拼接后的Wrap寻址

12930
来自专栏Pythonista

golang之切片与排序

排序操作在sort包中,sort.Ints对整数进行排序,sort.Strings对字符串进行排序,sort.Float64对浮点数进行排序

8020
来自专栏曾大稳的博客

OpenGLES顶点缓冲VBO

25120
来自专栏码匠的流水账

聊聊flink的AscendingTimestampExtractor

本文主要研究一下flink的AscendingTimestampExtractor

26410

扫码关注云+社区

领取腾讯云代金券