第四章 串串
定义
串，即字符串(String)是由零个或多个字符组成的有限序列
术语：串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的
位置
串[VS]线性表
串的数据对象限定为字符集
串的基本操作大多以“子串”为操作对象
基本操作
lndex(S,T)，定位操作，到串T在主串S中的位置
StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0;
若S<T，则返回值<0。
其他...
字符集编码
字符集
英文字符―—ASClI字符集
中英文―—Unicode字符集
每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数
的大小
串的存储结构
顺序存储
静态数组
动态数组malloc、free
链式存储可让每个结点存多个字符，没有字符的位置用'#'或'\O'补足
王道教材采用静态数组
基于顺序存储实现基本操作
求子串: bool SubString(SString &Sub,SString S, int pos, int len)
串的比较:int StrCompare(SString S, SString T)
求串在主串中的位置:int Index(sString S, SString T)
串的模式匹配
朴素模式匹配算法
原理：暴力破解
算法思想
主串长度n，模式串长度m
将主串中所有长度为m的子串与模式串比对
到第一个与模式串匹配的子串，并返回子串起始位置
若所有子串都不匹配，则返回0
最坏时间复杂度=O(nm)
KMP算法
不匹配的字符之前，一定是和模式串一致的
依赖于模式串，与主串没有关系
主要优点：主串指针不回溯
用一个next数组存储模式串指针
算法思想
根据模式串T，求出next数组
利用next数组进行匹配（主串指针不回溯）
对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字
符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t
j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大
的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即
next[ j ]=MAX{ k }
求next数组
next数组的作用：当模式串的第j个字符失配时，从模式串的第next[j]的继续向后
匹配
next[1]无脑写0
next[2]无脑写1
其他next：在不匹配的位置前，划一根美丽的分界线
模式串一步一步往后退，直到分界线之前全部匹配，或模式串完全跨过分界线为
止。此时j指向哪儿,next数组值就是多少
最坏时间复杂度=O(m+n)
KMP算法的优化求nextval数组
先求next数组
若next数组所对应位置的字符和当前字符相等，将对应位置的next数组赋值到当
前位置的nextval数组
子主题3字符串长度17模式串长度

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