图4-1 子串在主串中的位置
图4-2 字符串的顺序存储1
4字符串
4.1 字符串
4.2 模式匹配BF 算法
4.3 模式匹配KMP 算法
4.4 改进的KMP 算法
4.5 字符串的应用——病毒检测
4.6 字符串学习秘籍4.1 字符串
串：又称字符串，是由零个或多个字符组成的有限序列。字符串通常用双引号括起来，例如S=“abcdef”，S 为字符串的名字，双引号里面的内容为字符串的值。串长：串中字符的个数，例如S 的串长为6。
空串：零个字符的串，串长为0。
子串：串中任意个连续的字符组成的子序列，称为该串的子串，原串称为子串的主串。例如T=“cde”，T 是S 的子串。子串在主串中的位置，用子串的第一个字符在主串中出现的位置表示。T 在S 中的位置为3，如图4-1所示。 注意：空格也算一个字符，例如X=“abc fg”，X 的串长为6。空格串：全部由空格组成的串为空格串。
注意：空格串不是空串。
字符串的存储可以使用顺序存储和链式存储两种方式。
1．字符串的顺序存储
顺序存储是用一段连续的空间存储字符串。可以预先分配一个固定长度Maxsize 的空间，在这个空间中存储字符串。顺序存储又有3种方式。
（1）以'\0'表示字符串结束在C 、C++、Java 语言中，通常用'\0'表示字符串结束，'\0'不算在字符串长度内，如图4-2所示。
图4-3 字符串的顺序存储2
）结构体变量存储字符串的长度
除上述方法之外，也可以将字符串长度存储在结构体中。
{
Maxsize]; //字符型数组
//字符串的长度
S=“abdefgc”，其存储结构如图4-4所示。
图4-4 字符串的顺序存储3（静态分配）
这样做也有一个问题，串的运算如合并、插入、替换等操作，容易超过最大长度，出现溢出。为了解决这个问题，可以采用动态分配空间的方法，其结构体定义如下。
{
//指向字符串指针
//字符串的长度
S=“abcdef”，其存储结构如图4-5所示。
字符串的顺序存储3（动态分配） ### 2．字符串的链式存储
和顺序表一样，顺序存储的串在插入和删除操作时，需要移动大量元素，因此也可以采用链表的形式存
图4-6 字符串的链式存储1
图4-7 字符串的链式存储2
图4-8 第1次匹配开始
图4-9 第1次匹配不相等 2）i 回退到i−j+2的位置，j 回退到1的位置，即i−j+2=6−6+2=2，即i 从S 第2个字符开始，j 从T 第1个字符开始。比较两个字符是否相等，如果相等，则i++，j++；如果不等则转向下一
步，如图4-10所示。
单链表存储字符串时，虽然插入和删除非常容易，但是这样做也有一个问题：一个节点只存储一个字符，如果需要存储的字符特别多，会浪费很多空间。因此也可以考虑一个节点存储多个字符的形式，例如一个节点存储3个字符，最后一个节点不够3个时用#代替，如图4-7所示。
但是这样做也有一个大问题：如在第2个字符之前插入一个元素，就需要将b 和c 后移，那么这种后移还要跨到第二个节点，如同“蝴蝶效应”，一直波及最后一个节点，麻烦就大了！因此字符串很少使用链式
存储结构，还是使用顺序存储结构更灵活一些。
4.2 模式匹配BF 算法
模式匹配：子串的定位运算称为串的模式匹配（string pattern match ）或串匹配。假设有两个串S 、T ，设S 为主串，也称正文串；T 为子串，也称模式。在主串S 中查与模式T 相匹配的子串，如果查成功，返回匹配的子串第一个字符在主串中的位置。
字符串常量是由一对什么括起来的字符序列最笨的办法就是穷举所有S 的所有子串，判断是否与T 匹配，该算法称为BF （Brute Force 暴力）算法。算法步骤
1）从S 第1
个字符开始，与T 第
1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；
2）从S 第2个字符开始，与T 第1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；
3）从S 第3个字符开始，与T 第1个字符比较，如果相等，继续比较下一个字符，否则转向下一步；……
n ）如果T 比较完毕，则返回T 在S 中第一个字符出现的位置；如果S 比较完毕，则返回0，说明T 在S 中未出现。
完美图解
例如：S=“abaabaabeca”，T=“abaabe”，求子串T 在主串S 中的位置。
1）从S 第1个字符开始：i=1，j=1，如图4-8所示。比较两个字符是否相等，如果相等，则i++，j++；如果不等，则转向下一步，如图4-9所示。
次匹配不相等思考：为什么i要回退到
图4-11 串的匹配回退位置
i=2−1+2=3，即从S第3个字符开始，j=1，如图
；如果不等，则转向下一步，如图4-13
图4-12 第3次匹配开始
图4-13 第3次匹配不相等
的位置，i=4−2+2=4，即从S第4个字符开始，j=1，如图4-14所示。比较两个字符是否，j++；此时T比较完了，执行下一步，如图4-15所示。
图4-14 第4次匹配开始
）T比较完毕，返回子串T在主串S中第
i−m=10−6=4，m为T的长度。
图4-17 第1次匹配图4-18 第2次匹配图4-19 第3次匹配图4-20 第4次匹配

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。