文档介绍：串
串的基本概念及其抽象数据类型
串的存储结构
串类
串的模式匹配算法
本讲内容
串的基本概念
串(也称作字符串)是由n(n≥0)个字符组成的有限序列。
一个串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。
一个字符在一个串中的位置序号(为大于等于0的正整数)称为该字符在串中的位置。当且仅当这两个串的值完全相等时,称这两个串相等。
数据集合:串的数据集合可以表示为字符序列s0, s1,…, sn-1,每个数据元素的数据类型为字符类型。
操作集合:
(1)取字符charAt(index) :取index下标的字符返回。
(2)求长度length():返回串的长度。
(3)pareTo(anotherString):比较当前对象串和串anotherString的Unicode码值的大小。
(4)取子串substring(beginIndex, endIndex):取当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串
串的抽象数据类型
(5)连接concat(str):把串str连接到当前对象串的末尾。
(6)插入子串insert(str, pos):在当前对象串的第pos个字符前插入子串str。
(7)删除子串delete(beginIndex, endIndex):删除当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串。
(8)输出串值myPrint():输出当前对象的串值。
(9)查找子串index(subStr, start):在当前对象串的start下标开始,查找是否存在子串subStr。
串的抽象数据类型(Cont)
串的模式匹配
定义:在主串(目标串)中,从位置Start开始查找是否存在子串(模式串),若在目标串中找到一个与模式串相同的子串,则称查找成功,返回模式串中第一个字符在主串中的位置,若失败,则返回-1。
算法
Brute-Force
KMP
Brute-Force算法
(1)从主串s的第一个字符开始和模式串t的第一个字符比较,若相等则继续比较后续字符;
(2)若主串s的第一个字符和模式串t的第一个字符比较不相等,则从主串s的第二个字符开始重新与模式串t的第一个字符比较,若相等则继续比较后续字符
(3)若主串s的第二个字符与模式串t的第一个字符比较不相等,则从主串s的第三个字符开始重新与模式串t的第一个字符比较;
(4)如此不断继续。若存在模式串t中的每个字符依次和主串s中的一个连续字符序列相等,则模式匹配成功,函数返回模式串t的第一个字符在主串s中的下标;若比较完主串s的所有字符序列,不存在一个和模式串t相等的子串,则模式匹配失败,函数返回-1。
Brute-Force算法(Cont)
主串s=“cddcdc”,模式串t=“cdc”的模式匹配过程
朴素模式匹配算法的时间复杂度(主串长n; 子串长m。可能匹配成功的位置(1 ~ n-m+1))。
最好的情况:第i个位置匹配成功,比较了(i-1+m)次,时间复杂度O(n+m)。
最坏的情况:第i个位置匹配成功,比较了(i*m)次,比较次数:设n>>m,时间复杂度为O(n*m)。
Brute-Force算法的效率