编辑
2022-09-30
数据结构
00
请注意,本文编写于 626 天前,最后修改于 581 天前,其中某些信息可能已经过时。

目录

第四章 串
4.1 串
1. 定义
2. 存储类型
4.2 模式匹配算法
1. 简单的模式匹配算法
2. 改进的模式匹配算法——KMP算法

本章重点

串的定义与匹配

第四章 串

4.1 串

1. 定义

  • 串(string)s = 'a1a2a3...an'
  • n为串的长度,a可以是数字字母或其他字符(包括空格),0个字符成为空串
  • 主串:包含子串的串;
  • 子串:串中任意个连续的字符组成的子序列。

2. 存储类型

  • 定长顺序存储表示:用一组地址连续的存储单元存储串的字符序列。超过规定的最大长度时,串序列会被截断;
  • 堆分配存储表示:仍以一组地址连续的存储单元存放串值的字符序列,但存储空间是动态分配的,存在堆区,用malloc()申请,free()释放;
  • 块链存储表示:用链表存储,每个结点可以放一个或多个字符,每个结点称为块。

4.2 模式匹配算法

1. 简单的模式匹配算法

  • 逐个比较子串(模式串)和主串的字符,相同比较下一个,不相同则从主串+1处重新比较;
  • 每趟匹配失败都是主串后移一位再从子串的头开始比较。

2. 改进的模式匹配算法——KMP算法

  • 如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀,那么就可以将模式向后移动到与这些相等字符对其的位置,主串i指针无需回溯,并继续从该位置开始进行比较;
  • 前缀:除最后一个字符以外,字符串的所有头部子串;
  • 后缀:除第一个字符以外,字符串的所有尾部子串;
  • 部分匹配值(PM):前后缀中最长相等的前后缀长度;
  • next数组:下一次匹配时的位置。

提示:KMP算法

  • 我们可以用一个简单的流程来解释这个算法: 令主串'S'为:ABC ABCDAB ABCDABCDABDE; 令子串'W'为:ABCDABD; 令'm'为主串字符串位数,令'i'为子串字符串位数;

  • 第一轮:

    5_1.png S[3] != W[3]且前缀{A,AB}与后缀{C,CB}不同,故令m = 4, i = 0,继续比较;

  • 第二轮:

    5_2.png S[10] != W[6]但前缀{A,AB,ABC,ABCD,ABCDA}与后缀{B,AB,DAB,CDAB,BCDAB}有最长相等前后缀长度为2,故接下来从S[8]开始比较,令m = 8, i = 0继续比较;

  • 第三轮:

    5_3.png S[10] != W[2]且前缀{A}与后缀{B}不同,故令m = 11, i = 0,继续比较;

  • 第四轮:

    5_4.png S[17] != W[6]且前缀{A,AB,ABC,ABCD,ACBDA}与后缀{B,AB,DAB,CDAB,BCDAB}有最长相等前后缀长度为2,故接下来从S[15]开始比较,令m = 15, i = 0继续比较;

  • 第五轮:

    5_5.png S[21] == W[6]比较完成,其起始位置在S[15]

  • 设有字符串S = 'abbaabaabaac', P = 'aabaac'; 1⃣ 求P的next数组。2⃣ 若S作为主串,P作为模式串,试给出KMP的匹配过程。

  • 【解】 1⃣ 步骤一:通过前缀、后缀求出字符串的部分匹配值(PM) 'a'的前缀和后缀都是空集,最长相等前后缀长度0; 'aa'的前缀为{a},后缀为{a},最长相等前后缀长度1; 'aab'的前缀为{a,aa}后缀为{b,ab},最长相等前后缀长度0; 'aaba'的前缀为{a,aa,aab}后缀为{a,ba,aba},最长相等前后缀长度1; 'aabaa'的前缀为{a,aa,aab,aaba}后缀为{a,aa,baa,abaa},最长相等前后缀长度2; 'aabaac'的前缀为{a,aa,aab,aaba,aabaa}后缀为{c,ac,aac,baac,abaac},最长相等前后缀长度0; 故字符串P的部分匹配值为:010120; 步骤二:根据PM计算next数组:首个为0,填入前一个序号的PM值加一,即next[i] = PM[i-1]+1

    模式串aabaac
    序号123456
    PM010120
    next012123

    2⃣ KMP匹配过程:

    主串aabaabaabaac
    第一次比较aabaac
    第二次比较aabaac
    都三次比较aabaac
    • 第一次匹配:从主串和子串的第一个字符开始比较,i = 6 ,j = 6时失败;
    • 第二次匹配:next[6] = 3,主串当前位置和子串的第三个字符比较,i = 9, j = 6 时失败;
    • 第三次匹配:next[6] = 3,主串当前位置和子串的第三个字符比较,匹配成功。
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:Handy Zhang

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!