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

相关文章

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

泛函编程(9)-异常处理-Option

     Option是一种新的数据类型。形象的来描述:Option就是一种特殊的List,都是把数据放在一个管子里;然后在管子内部对数据进行各种操作。所以Op...

1726
来自专栏JAVA高级架构

Java 内存模型 JMM 浅析

JMM简介 Java Memory Model简称JMM, 是一系列的Java虚拟机平台对开发者提供的多线程环境下的内存可见性、是否可以重排序等问题的无关具体平...

3339
来自专栏武培轩的专栏

Object源码解析(JDK1.8)

1 package java.lang; 2 3 4 public class Object { 5 6 /** 7 ...

2745
来自专栏专注 Java 基础分享

使用 Synchronized 关键字

使用 Synchronized 关键字来解决并发问题是最简单的一种方式,我们只需要使用它修饰需要被并发处理的代码块、方法或字段属性,虚拟机自动为它加锁和释放锁,...

693
来自专栏木木玲

深入解析 volatile 、CAS 的实现原理

1411
来自专栏项勇

笔记 35 | java线程之线程安全与非线程安全

1595
来自专栏专注 Java 基础分享

Java并发之synchronized关键字

     上篇文章我们主要介绍了并发的基本思想以及线程的基本知识,通过多线程我们可以实现对计算机资源的充分利用,但是在最后我们也说明了多线程给程序带来的两种典型...

1915
来自专栏专注 Java 基础分享

CAS 无锁式同步机制

计算机系统中,CPU 和内存之间是通过总线进行通信的,当某个线程占有 CPU 执行指令的时候,会尽可能的将一些需要从内存中访问的变量缓存在自己的高速缓存区中,而...

732
来自专栏用户2442861的专栏

Java中Synchronized的用法

原文:http://blog.csdn.net/luoweifu/article/details/46613015 作者:luoweifu 转载请标名...

371
来自专栏编码前线

synchronized锁住的是代码还是对象

在Java中,synchronized关键字是用来控制线程同步的,就是在多线程的环境下,控制synchronized代码段不被多个线程同时执行。synchron...

542

扫码关注云+社区