算法:字符串的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 条评论
登录 后参与评论

相关文章

来自专栏天天

框架设计续集(六)

834
来自专栏武培轩的专栏

京东2019春招Java工程师编程题题解

生成回文串 题目描述 对于一个字符串,从前开始读和从后开始读是一样的,我们就称这个字符串是回文串。 例如"ABCBA","AA","A"是回文串,而"ABCD"...

2938
来自专栏咸鱼不闲

jsoup爬虫工具的简单使用

解决方案: 1.通过url 获得doucment对象, 2.调用select()等方法获得Elements对象, 3.调用.text()等方法,获得自己想要的内...

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

《Kotlin 程序设计》第十一章 Kotlin实现DSL

DSL 即 domain-specific languages,领域特定语言。和一般的编程语言不同,领域特定语言只能用于特定的领域中并且表现形式有限。领域特定语...

1012
来自专栏Golang语言社区

Go语言 枚举和类型

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

3478
来自专栏曾大稳的博客

OpenGLES顶点缓冲VBO

1272
来自专栏aCloudDeveloper

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

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

2086
来自专栏曾大稳的博客

OpenGLES添加水印

理解了添加水印的原理,不管是视频水印还是图片水印都是很简单的了,只是使用的纹理不一样而已。如果是绘制文字水印的话,则需要将文字生成图片,然后将图片使用纹理绘制即...

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

Scala类型推导Scala类型推导

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

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

纹理拼接后的Wrap寻址

1073

扫码关注云+社区