串赋值操作 StrAssign(s, t) :将串 t 赋值给串 s ,即将串 t 的值复制给串 s 。
(2)StrCopy(串复制操作 StrCopy(t, s)) :由串 s 复制得到一个与 s 相等的新串 t 。
(3)StrCompare(串比较操作 StrCompare(s, t)) :比较两个串 s 和 t 的大小关系,若 s=t 则返回0,若 s<t 则返回负数,若 s>t 则返回正数。
(4)StrLength(求串长操作 StrLength(s)) :返回串 s 的长度。
(5)Concat(串连接操作 Concat(t, s1, s2)) :将两个串 s1 和 s2 连接起来,得到一个新串 t 。
(6)SubString(求子串操作 SubString(sub, s, pos, len)) :返回串 s 中从第 pos 个字符起长度为 len 的子串 sub 。
(7)Index(串匹配操作 Index(s, t, pos)) :在串 s 中从第 pos 个字符开始查找子串 t ,若存在则返回子串 t 在串 s 中的位置,否则返回0。
4.2 串的存储结构
串的存储结构有两种:顺序存储结构和链式存储结构。
(1) 顺序存储结构:
顺序存储结构是将串的字符依次存储在一片连续的存储空间中,通过定长数组实现。串的长度与数组的大小相关联,不易修改。
(2) 链式存储结构:
链式存储结构是将串的字符存储在链表中,每个节点存储一个字符。串的长度可以动态增加,灵活方便,但操作复杂度较高。
4.3 串的模式匹配
串的模式匹配是指在一个串中查找另一个子串的过程,常用于字符串匹配、搜索、替换等操作。串的模式匹配算法有很多,其中较为著名的有暴力匹配算法、KMP算法、Boyer-Moore算法等。
(1) 暴力匹配算法:
暴力匹配算法是最简单的一种匹配算法,即通过遍历主串和模式串的每个字符,进行逐个比较,若匹配失败则主串指针回溯重新开始匹配。
(2) KMP算法:
KMP算法是一种高效的模式匹配算法,通过预处理模式串构建next数组,利用next数组中的信息来指导主串和模式串的匹配过程,有效减少了比较次数。
(3) Boyer-Moore算法:
Boyer-Moore算法是一种基于坏字符规则和好后缀规则的字符串匹配算法,通过预处理模式串构建badchar数组和suff数组,利用这两个数组中的信息来加速匹配过程,提高匹配效率。
本章小结
本章主要介绍了串的基本概念、存储结构以及模式匹配。串是由零个或多个字符组成的有穷序列,常用于处理字符序列操作。串的存储结构有顺序存储结构和链式存储结构两种形式,每种存储结构都有其优缺点。串的模式匹配是一种常见的字符串匹配操作,涉及到暴力匹配、KMP算法、Boyer-Moore算法等多种算法。合理选择匹配算法能够提高字符串匹配的效率和准确性,对于处理字符串操作具有重要意义。"