山西网站建设费用,做网站多少钱西宁君博正规,建筑行业信息平台,站酷网电脑版第四章 串
4.1 串的定义
4.1.1 串的相关概念 串#xff1a;即字符串#xff08;String#xff09;是由零个或多个字符组成的有限序列。一般记为S‘a1a2…an’ (n0) 其中S是串名#xff0c;单引号#xff08;注#xff1a;有的地方用双引号#xff0c;如Java、C即字符串String是由零个或多个字符组成的有限序列。一般记为S‘a1a2…an’ (n0) 其中S是串名单引号注有的地方用双引号如Java、C有的地方用单引号如Python括起来的字符序列是串的值ai可以是字母、数字或其他字符。 串的长度串中字符的个数 nn 0 时的串称为空串用∅\emptyset∅表示。 子串串中任意个连续的字符组成的子序列。 主串包含子串的串。 字符在主串中的位置字符在串中的序号。(注意位序从1开始而不是从0开始) 子串在主串中的位置子串的第一个字符在主串中的位置 。 空串 vs 空格串 M‘’ M是空串 N’ ’ N是由三个空格字符组成的字符串每个空格字符占1B 串 vs 线性表 ① 串是一种特殊的线性表数据元素之间呈线性关系 ② 串的数据对象限定为字符集如中文字符、英文字符、数字字符、标点字符等 ③ 串的基本操作如增删改查等通常以字串为操作对象
4.1.2 串的基本操作
StrAssign(T, chars)赋值操作。把串 T 赋值为 chars。StrCopy(T, S)复制操作。由串 S 复制得到串 T。StrEmpty(S)判空操作。若 S 为空串则返回 TRUE否则返回 FALSE。StrLength(S)求串长。返回串 S 中元素的个数。ClearString(S)清空操作。将 S 清为空串。DestroyString(S)销毁串。将串 S 销毁回收存储空间。Concat(T, S1, S2)串联接。用 T 返回由 S1 和 S2 联接而成的新串 。SubString(Sub, S, pos, len)求子串。用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。Index(S, T)定位操作。若主串 S 中存在与串 T 值相同的子串则返回它在主串 S 中第一次出现的位置否则函数值为 0。StrCompare(S, T)比较操作。若 ST则返回值0若 ST则返回值0若 ST则返回值0。
4.1.3 串的存储结构
1、静态数组实现定长顺序存储
#define MAXLEN 255 //预定义最大串长为255
typedef struct {char ch[MAXLEN]; // 每个分量存储一个字符int length; // 串的实际长度
} SString;2、动态数组实现堆分配存储
typedef struct {char *ch; // 按串长分配存储区ch指向串的基地址int length; // 串的长度
} HString;
HString S;
S.ch(char *)malloc(MAXLEN*sizeof(char)); //用完需要手动free
S.length0;3、块链存储表示 默认情况下存储密度低每个节点都只能存储一个字符 解决方法一个结点存储多个字符 typedef struct StringNode{char ch; //存储密度低每个字符1B每个指针4Bstruct StringNode * next;
}StringNode,* String;typedef struct StringNode{char ch[4];struct StringNode *next;
}StringNode,* String; //存储密度提高4.2 串的模式匹配 串的模式匹配在主串中找到与模式串相同的子串并返回其所在位置。 4.2.1 简单的模式匹配算法
思想将主串中与模式串长度相同的字串拿出来挨个与模式串对比
当子串与模式串某个对应字符不匹配时就立即放弃当前子串转而检索下一个子串
一个示例 分析 简单模式匹配算法的最坏时间复杂度是O(nm)即每个子串都要对比到最后一个字符如下面这种情况 主串1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2子串1 1 1 1 1 1 1 1 2 其中n和m分别是主串和模式串的长度。 最好的情况对于每个子串都只需对比一次 匹配成功O(m)匹配失败O(n-m1)O(n-m)≈O(n) 4.2.2 KMP算法
朴素模式匹配算法的缺点当某些子串与模式串能部分匹配时主串的扫描指针i经常回溯导致时间开销增加。
要了解子串的结构首先需要了解以下几个概念前缀、后缀和部分匹配值。
前缀除了最后一个字符外字符串的所有头部子串
后缀除了第一个字符外字符串的所有尾部子串 ‘ab’的前缀是{a}后缀是{b}{a}∩{b}∅最长相等前后缀长度为0 aba’的前缀为{a, ab}后缀为{a, ba}, {a, ab }∩{a, ba}{a)最长相等前后缀长度为1。 abab 的前缀{a, ab,aba}∩后缀{b, ab, bab }{ab}最长相等前后缀长度为2。 ababa 的前缀{a, ab,aba, abab }∩后缀{a , ba, aba, baba }{a, aba}公共元素有两个最长相等前后缀长度为3。 故字符串’ababa’的部分匹配值为00123 接下来详解一下上面这个例子
由上述方法求子串’abcac’的部分匹配值 ab’的前缀{a},后缀{b} {a}∩{b} ∅ abc’的前缀{a,ab}, 后缀{c, bc} {a,ab}∩{c, bc} ∅ abca’的前缀{a,ab,abc},后缀{a,ca,bca} {a,ab,abc}∩{a,ca,bca} {a} abcac’的前缀{a,ab,abc,abca},后缀{c,ac,cac,bcac} {a,ab,abc}∩{c,ac,cac,bcac} ∅ 将其部分匹配值写成数组形式就得到了部分匹配值PM的表
编号12345SabcacPM00010
接下来可以使用PM表来进行字符串匹配其过程如下 KMP算法的原理
当c与b不匹配时已匹配’abca’的前缀a和后缀a为最长公共元素。已知前缀a与b、c均不同与后缀a相同故无须比较直接将子串移动“已匹配的字符数–对应的部分匹配值”用子串前缀后面的元素与主串匹配失败的元素开始比较即可。 对算法的改进
已知:右移位数已匹配的字符数-对应的部分匹配值。写成 Move(j−1)−PM[j−1]Move(j-1)-PM[j-1] Move(j−1)−PM[j−1] 现在这种情况下我们在匹配失败时需要去查找它前一个元素的部分匹配值这样使用起来有点不方便故我们可以将PM表右移一位这样哪个元素匹配失败则直接看它自己的部分匹配值即可。
将上例的PM表右移一位则得到了next数组
编号12345Sabcacnext-10001
我们注意到
1第一个元素右移以后空缺的用-1来填充因为若是第一个元素匹配失败则需要将子串向右移动一位而不需要计算子串移动的位数。 2最后一个元素在右移的过程中溢出因为原来的子串中最后一个元素的部分匹配值是其下一个元素使用的但显然已没有下一个元素故可以舍去。
这样上式就改写为 Move(j−1)−next[j]Move(j-1)-next[j] Move(j−1)−next[j] 就相当于将子串的比较指针回退到 jj−Movej−((j−1)−next[j])next[j]1jj-Movej-((j-1)-next[j])next[j]1 jj−Movej−((j−1)−next[j])next[j]1 但为了让公式更加简洁我们将next数组整体加1
next数组也可以写成:
编号12345Sabcacnext01112
最终子串指针变化公式为 jnext[j]jnext[j] jnext[j] 在实际匹配过程中子串在内存里是不会移动的而是指针在变化书中画图举例只是为了让问题描述得更加形象。next[j]的含义是:在子串的第j个字符与主串发生失配时则跳到子串的next[j]位置重新与主串当前位置进行比较。 【重要】求next数组根据如下示例来学习 KMP算法的进一步优化 问题的产生 所以引入了nextval数组对KMP算法进行进一步优化。
故我们在模式串中当前模式串p和对应的next数组p_next的模式串值相等时继续查找对应p_next模式串的next数组对应的模式串直到模式串对应的值不相等。
以下是匹配过程
