尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:257
已运行时间:
目录
  1. Brute-Force
  2. KMP 算法
    1. 算法详述
    2. 计算 next 函数值
    3. 计算 next 函数修正值
    4. 具体匹配情况
    5. 代码

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情

站点信息

文章数目:257
已运行时间:

image.png

在进行字符串匹配的相关程序中,看一个子串是否在一个主串里面,有著名的Brute-Force和基于此改进的KMP算法,具体学习记录如下:

Brute-Force

给出一个主串和一个子串
主串:s = ababcabcacbab
子串:t = abcac

①BF 算法算是一种暴力算法,首先是查看 t 的第一字母 a 和上面 s 的第一个字母比较相同,所以接着比较比到各自的第三个字符也就是,aba、abc 发现不同,

② 再递推比较,t 回到第一个字母 a,这时 s 回到第二个字符(因为第一个字符已经比过了)相当于 babcabcacbab 和 abcac 两个字符串进行比较,很明显第一个字符就不一样,

③ 再递推比较……

按常理来思考,这样总能得出结果,但是在此基础上,可以有进一步的优化操作,怎么说?huaji1558a846ddf2e12b.jpeg
在上面的第 ② 步里面,我们总是一步一步递推,那我们能不能一次性推好几步呢?就根据已经匹配了的那串字母。

具体表现为:① 已经发现是第三个字符不同,那我们就根据前面两个相同的字符(ab)推出第 ② 步推两步,为什么根据相同的 ab,第 ② 个步骤就可以一次性走两步?

KMP 算法

算法详述

huaji1558a846ddf2e12b.jpeg先学会用,理论日后再补…… 🕊

image.png

计算 next 函数值

(3)串“ababaaababaa”的 next 数组为(  )。
A.012345678999   B.012121111212   C.011234223456    D.0123012322345
答案:C

j 1 2 3 4 5 6 7 8 9 10 11 12
t a b a b a a a b a b a a
next(j) 0 1 1 2 3 4 2 2 3 4 5 6

方法:
①next 数组第一位永远是 0,1;
②next(j) = 前序列相同元素个数 + 1;

eg:当 t = 6:
前面的序列为 ababa,可以看出相同的子序列为 aba,相同元素个数为 3,所以 next(6) = 3 + 1 = 4

注意:不能“全覆盖”,比如当 j = 2 时候,前面的 a 不能看成 a = a 序列,这样就变成 next(2) = 2 了;

计算 next 函数修正值

(4)串“ababaabab”的 nextval 为(  )。
A.010104101      B.010102101      C.010100011       D.010101011  
答案:A

j 1 2 3 4 5 6 7 8 9
t a b a b a a b a b
next(j) 0 1 1 2 3 4 2 3 4
nextval(j) 0 1 0 1 0 4 1 0 1

方法:
① 先列举出 next(j),求 nextval(j)是基于 next(j)的;
② 求 nextval(j),先看求 next(j)的值,记这个值为 x;
③ 在表格中找出 j = x 的那一列,如果这一列的 t 值和 ② 步骤中的 t 值相同,则结果为 j = x 这一列的 nextval(j)值,如果不相同,则结果为所要求的那一列的 next(j)值;

eg:当 j = 5 时:
此时 next(j) = 3,就去 j = 3 那一列看到 t = a,和 j = 5 一列的 t 值 a 相同,所以结果为 j = 3 一列的 nextval 值 0

eg:当 j = 6 时:
此时 next(j) = 4,就去 j = 4 那一列看到 t = b,和 j = 6 一列的 t 值不相同,所以结果为 j = 6 一列的 next 值 4

具体匹配情况

(2)设目标为 t=“abcaabbabcabaacbacba”,模式为 p=“abcabaa”
① 计算模式 p 的 naxtval 函数值;
② 不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。

答案:
image.png

代码

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int ElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1

//------串的顺序存储结构-----
#define MAXLEN 225
typedef struct
{
    char ch[MAXLEN + 1];    //存储串的一维数组,从下标为1的数组分量开始存储的,下标为0的分量闲置不用
    int length;             //串的当前长度
}SString;

//------串的堆式顺序存储结构-----
typedef struct
{
    char *ch;       //若是非空串,则按串长分配存储区,否则ch为NULL
    int length;     //串的当前长度
}HString;

HString S, T;

//-----串的链式存储结构-----
#define CHUNKSIZE 80
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head, *tail;     //串的头指针和尾指针
    int length;             //串的当前长度
}LString;

// //1、生成串
// StrAssign(&T, chars)

// //2、复制
// StrCopy(&T, S)

// //3、判空
// StrEmpty(S)

// //4、比较
// StrCompare(S, T)

// //5、长度
// StrLength(S)

// //6、清空
// ClearString(&S)

// //7、联接
// Concat(&T, S1, S2)

// //8、子串
// SubString(⋐, S, pos, len)

//9、串的模式匹配_BF算法 O(n * m)
int Index_BF(HString S, HString T, int pos)
{//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在,则返回值为0
 //其中,T非空,1<=pos<=S.length
    int i = pos, j = 1;                     //初始化
    while(i <= S.length && j <= T.length)   //两串均未比较到串尾
    {
        if(S.ch[i] == T.ch[j])              //继续比较后继字符
        {
            i++;
            j++;
        }
        else                                //指针后退重新开始匹配
        {
            i = i - j + 2;                  //i=i-j+1回到i的起点,+2到下一个字符
            j = 1;
        }
    }
    if(j > T.length)
            return i - T.length;            //匹配成功,返回T在S中第一次出现的位置
        else
            return 0;
}

//9、串的模式匹配_KMP算法求next数组
void get_next(HString, int next[])
{//求模式串T的next函数值并存入数组next
    int j = 1, t = 0;
    next[1] = 0;
    while(j < T.length)
    {
        if(t == 0 || T.ch[j] == T.ch[t])
        {
            t++;
            j++;
            next[j] = t;
        }
        else
            t = next[t];
    }
}

//9、串的模式匹配_KMP算法求nextval数组
void get_nextval(HString T, int nextval[])
{//求模式串T的next函数修正值并存入数组nextval
    int j = 1, t = 0;
    nextval[1] = 0;
    while(j < T.length)
    {
        if(t == 0 || T.ch[j] == T.ch[t])
        {
            t++;
            j++;
            if(T.ch[j] != T.ch[t])
                nextval[j] = t;
            else
                nextval[j] = nextval[t];
        }
        else
            t = nextval[t];
    }
}

//9、串的模式匹配_KMP算法 O(n + m)
int Index_KMP(HString S, HString T, int pos, int next[])
{//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
 //其中,T非空,1<=pos<=S.length
    int i = pos, j = 1;
    while(i <= S.length && j <= S.length)   //两个串均未比较到串尾
    {
        if(j == 0 || S.ch[i] == T.ch[i])    //继续比较后继字符
        {
            i++;
            j++;
        }
        else
            j = next[j];                    //模式串向右移动
        if(j > T.length)                    //匹配成功
            return i - T.length;
        else
            return 0;
    }
}

// //10、插入
// Strlnsert(&S, pos, T)

// //11、删除
// StrDelete(&S, pos, len)

// //12、销毁
// DestroyString(&S)

评论区

Beaudar Twikoo

最新评论

Loading...