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

相关文章

来自专栏PHP在线

坐在马桶上看算法(2):邻居好说话,冒泡排序

原文出处: 纪磊 简化版的桶排序不仅仅有上一节所遗留的问题, 更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000之间,那你则需要申请2...

2856
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

932
来自专栏ACM算法日常

最高的牛Tallest Cow(前缀和)- POJ 3263

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. E...

921
来自专栏生信小驿站

数据处理第3部分:选择行的基本和高级的方法

原文地址:https://suzan.rbind.io/2018/02/dplyr-tutorial-3/ 作者:Suzan Baert 这是系列dplyr...

651
来自专栏计算机视觉与深度学习基础

Leetcode 189 Rotate Array

Rotate an array of n elements to the right by k steps. For example, with n = 7...

1795
来自专栏小樱的经验随笔

华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood ? B.Choosy in Food •F[i]:从第I个点到终点的期望步数 •F[i] = (F[i +...

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

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

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

1725
来自专栏Felix的技术分享

【LeetCode】Merge Intervals

1445
来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

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

JavaScript学习笔记002-数据类型0字符串拼接

[十位] [个位] [几何] [子集] [大圆] [小圆] [元素] [下标] [分子] [分母] [分数] [中点] [约分] [加数] [减数]

791

扫码关注云+社区