考研笔记

串的定义与简单的模式匹配

4.1 整节标了 *，教材脚注：「本节不在统考大纲范围，仅供学习参考。」 第 4 章的考纲内容只有一句「字符串模式匹配」。本页把 4.1 的几个定义压缩成一张表，重点放在 4.2.1 的简单模式匹配：它是 KMP 的出发点，KMP 的每一处改进都是针对它的某个缺点。

机制

*4.1 串的定义、基本操作与存储

串（string）是由零个或多个字符组成的有限序列，记为 。

概念定义
串长串中字符的个数
空串 的串，用 表示
空格串由一个或多个空格组成的串。空格串不是空串，其长度为空格字符的个数
子串 / 主串串中任意多个连续的字符组成的子序列称为子串；包含子串的串称为主串
位置字符在串中的序号；子串的位置以子串第 1 个字符在主串中的位置表示
串相等长度相等且每个对应位置的字符都相等

例： 'China Beijing'、 'Beijing'、 'China'，长度分别为 13、7、5； 在 中的位置是 7， 的位置是 1。空格也算一个字符。

串与线性表：逻辑结构极为相似，区别仅在于串的数据对象限定为字符集。基本操作差别很大：线性表以单个元素为操作对象，串通常以子串为操作对象。

最小操作子集：StrAssign（赋值）、StrCompare（比较）、StrLength（求串长）、Concat（联接）、SubString（求子串）五种操作不能用其他串操作实现；其他串操作（除 ClearString 和 DestroyString 外）都可以在这个子集上实现。Index(S,T) 是定位操作，不在最小子集中。

存储方式要点
定长顺序存储定长数组 char ch[MAXLEN]；超过预定义长度的串值会被舍去，称为截断。串长可以用额外变量 length 存放，也可以在串值后加不计入串长的结束标记 '\0'（隐含值）
堆分配存储仍是一组地址连续的存储单元，但存储空间在程序执行中动态分配（malloc/free）
块链存储类似链式存储；每个结点称为块，可存放一个或多个字符，最后一个结点占不满时通常用 # 补上

前两种通常为高级程序设计语言所采用；块链存储仅做简单介绍。

4.2.1 简单的模式匹配算法

模式匹配：在主串中找到与模式串相同的子串，并返回其所在的位置。教材采用定长顺序存储，给出一种不依赖其他串操作的暴力匹配算法：

int Index(SString S, SString T){
    int i=1, j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i]==T.ch[j]){ ++i; ++j; }   // 继续比较后继字符
        else{ i=i-j+2; j=1; }               // 指针后退重新开始匹配
    }
    if(j>T.length) return i-T.length;
    else return 0;
}

失配时 i=i-j+2：本趟从主串的第 个字符开始比，下一趟从它的下一个位置 开始。这就是主串指针的回溯。

复杂度：设主串和模式串的长度分别为 和 ，最多需要进行 趟匹配，每趟最多比较 次，最坏时间复杂度为 。

教材的最坏情况例子：模式串 '0000001'，主串的前 45 个字符均为 '0'、第 46 个为 '1'。每趟都比较到模式串的最后一个字符才发现不等，指针 回溯 39 次，总比较次数为 次（已用程序复核）。

低效的根源：每次回溯后，已匹配的那段主串字符被重新拿来和模式串比较，而这段字符其实就是模式串的某个前缀，可以事先分析。KMP 正是从这一点入手的。

边界

说法判断说明
「空格串就是空串」❌空格串的长度为空格字符的个数；空串长度为 0
「子串可以由不连续的字符组成」❌子串必须是连续的字符
「串的基本操作和线性表一样以单个元素为对象」❌串通常以子串为操作对象
「Index 属于最小操作子集」❌最小子集是赋值、比较、求串长、联接、求子串
「堆分配存储是链式存储」❌仍是地址连续的存储单元，只是空间动态分配
「求 在 中首次出现的位置称为求子串」❌称为模式匹配。求子串是从串中截取第 个字符起长度为 的子串
「简单模式匹配的时间复杂度是 」❌理论上是 。一般情况下实际执行时间近似 ，这是它至今仍被采用的原因
「4.1 在统考大纲范围内」❌教材脚注：不在统考大纲范围，仅供学习参考

考点

  • 空串与空格串；子串的位置用第一个字符的位置表示。
  • 简单模式匹配：失配时 i=i-j+2、j=1；最坏 。
  • 理论复杂度与实际执行时间的区别（4.2.4 第 3 题）。

链接

反向链接