|
|
|
|
知识路径： > 计算机系统基础知识 > 计算机软件知识 > 数据结构与算法知识 >
|
|
|
被考次数：7次
|
|
|
被考频率：
中频率
|
|
|
总体答错率：
47%
|
|
知识难度系数：
|
|
|
考试要求：
掌握
|
|
|
相关知识点：7个
|
|
|
|
|
|
|
串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S='a1a2…an'，其中S是串名，a1a2…an是串值。
|
|
|
|
|
|
|
|
|
|
（3）子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
|
|
|
|
（4）串相等：指两个串长度相等且对应位置上的字符也相同。
|
|
|
|
（5）串比较：两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
|
|
|
|
|
|
（1）赋值操作StrAssign(s,t)：将串t的值赋给串s。
|
|
|
|
（2）连接操作Concat(s,t)：将串t接续在串s的尾部，形成一个新串。
|
|
|
|
（3）求串长StrLength(s)：返回串s的长度。
|
|
|
|
（4）串比较StrCompare(s,t)：比较两个串的大小。
|
|
|
|
（5）求子串SubString(s,start,len)：返回串s中从start开始的、长度为len的字符序列。
|
|
|
|
|
|
|
|
串的顺序存储结构是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。
|
|
|
|
|
|
串也可采用链表方式作为存储结构，当用链表存储串中的字符时，每个节点中可以存储一个字符，也可以存储多个字符，要考虑存储密度的问题。在链式存储结构中，节点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串处理的效率。
|
|
|
|
|
|
子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。
|
|
|
|
|
|
朴素的模式匹配算法也称为布鲁特一福斯算法，其基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。
|
|
|
|
该算法在最好情况下匹配算法的时间复杂度为O(n+m)，而在最坏情况下的时间复杂度为O(n×m)。
|
|
|
|
|
|
改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的指针，而是利用已经得到的"部分匹配"的结果，将模式串向后"滑动"尽可能远的距离，再继续进行比较。
|
|
|
|
|
