第4章 串 4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法.

Presentation on theme: "第4章 串 4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法."— Presentation transcript:

1 第4章 串 4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法

2 本章主要知识点： 串的基本概念 串的存储结构 串类的设计方法，主要是拷贝、插入子串和删除子串的设计方法 串的模式匹配算法，包括Brute-Force算法和KMP算法

3 4.1 串的基本概念及其抽象数据类型 4.1.1 串的基本概念 串（也称作字符串）是由n（n≥0）个字符组成的有限序列。
一个串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串称为该子串的主串。 一个字符在一个串中的位置序号（为大于等于0的正整数）称为该字符在串中的位置。当且仅当这两个串的值完全相等时，称这两个串相等。

4 4.1.2 串的抽象数据类型 数据集合：串的数据集合可以表示为字符序列s0, s1,… , sn-1，每个数据元素的数据类型为字符类型。 操作集合： （1）取字符charAt(index) ：取index下标的字符返回。 （2）求长度length()：返回串的长度。 （3）比较compareTo(anotherString)：比较当前对象串和串anotherString的Unicode码值的大小。 （4）取子串substring(beginIndex, endIndex)：取当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串

5 （5）连接concat(str)：把串str连接到当前对象串的末尾。
（6）插入子串insert(str, pos)：在当前对象串的第pos个字符前插入子串str。 （7）删除子串delete(beginIndex, endIndex)：删除当前对象串中从beginIndex下标开始、至endIndex下标的前一下标止的子串 。 （8）输出串值myPrint()：输出当前对象的串值。 （9）查找子串index(subStr, start)：在当前对象串的start下标开始，查找是否存在子串subStr。

6 4.2 串的存储结构 1 串的顺序存储结构 串的顺序存储结构就是用字符类型数组存放串的所有字符。 表示串的长度通常有两种方法：
（1）设置一个串的长度参数。 （2）在串值的末尾添加结束标记。

7 串值长度的第一种表示方法下，串的成员变量应包括如下两项：
char[] value; int count; 其中，value为存储串值的字符类型数组名，count表示串值的长度。

8 2 串的链式存储结构 串的链式存储结构就是把串值分别存放在构成链表的若干个结点的数据元素域上。 有单字符结点链和块链两种。 单字符结点链就是每个结点的数据元素域只包括一个字符。 块链就是每个结点的数据元素域包括若干个字符。

9 4.3 串类 4.3.1 MyString类 4.3.2 MyString类的测试 4.3.3 MyStringBuffer类

10 4.4 串的模式匹配算法 4.4.1 Brute-Force算法
（1）从主串s的第一个字符开始和模式串t的第一个字符比较,若相等则继续比较后续字符； （2）若主串s的第一个字符和模式串t的第一个字符比较不相等，则从主串s的第二个字符开始重新与模式串t的第一个字符比较，若相等则继续比较后续字符

11 （3）若主串s的第二个字符与模式串t的第一个字符比较不相等，则从主串s的第三个字符开始重新与模式串t的第一个字符比较；
（4）如此不断继续。若存在模式串t中的每个字符依次和主串s中的一个连续字符序列相等，则模式匹配成功，函数返回模式串t的第一个字符在主串s中的下标；若比较完主串s的所有字符序列，不存在一个和模式串t相等的子串，则模式匹配失败，函数返回-1。 设主串s=“cddcdc”,模式串t=“cdc”,模式匹配过程如图：

12

13 一个比较极端的例子

14 Brute-Force算法模式匹配的一般性过程如图 ：

15 KMP算法 Brute-Force算法的缺点以及解决方法分析 KMP算法是在Brute-Force算法基础上的改进算法。KMP算法的特点主要是，消除了Brute-Force算法的主串比较位置在相当多个字符比较相等后，只要有一个字符比较不相等，主串位置便需要回退的缺点。 Brute-Force算法的匹配过程可以发现，算法中的主串比较位置的回退并非一定必要。这可分两种情况:

16 （1）第一种情况。主串s=“cddcdc”、模式串t=“cdc”的模式匹配过程为：当s0=t0，s1=t1，s2≠t2时，算法中下一次的比较位置为i=1,j=0，即下来比较s1和t0。但是因t0≠t1，而s1=t1，所以一定有s1≠t0。所以此时比较s1和t0无意义，实际上随后可直接比较s2和t0。 （2）第二种情况。主串s=“abacabab”、模式串t=“abab”的第一次匹配过程如图4-5所示。此时有s0＝t0＝’a’，s1＝t1＝’b’，s2＝t2＝’a’，s3≠t3。因有t0≠t1，s1=t1，所以必有s1≠t0。又因有t0=t2，s2=t2，所以必有s2=t0，因此下来可直接比较s3和t1。

17 考虑上面的图，M中灰色部分已经和S的灰色部分匹配上了，而灰色部分后一个字符不匹配，则现在M要向后滑动，假设一直向后滑动，直到如图位置又和S再一次匹配上了，那么从这里我们可以得到如下的结论：
A段字符串是M的一个前缀。 B段字符串是M的一个后缀。 A段字符串和B段字符串相等。

18 我们的任务就是要寻找subM的最长的前缀和后缀相等的串。
这样，如果暂时不考虑S，只看M的话，假设已经匹配的M的字串(即图中M中灰色部分)为subM，则subM有个【相等】的【前缀】和【后缀】。而且M在遇到不匹配的时候可以直接滑动到使subM的前缀和subM的后缀重合的地方。而M向后滑动的时候，第一次subM的前缀和后缀重合意味着此时这个相等的subM的前缀和后缀的长度是最大的。 我们的任务就是要寻找subM的最长的前缀和后缀相等的串。

19 我们假设 主串第i个字符与模式串的第j(j<=m）个字符‘失配’后，主串第i个字符与模式串的第k(k<j）个字符继续比较 此时，s(i）≠p(j），有 主串：s⑴…… s(i-j+1）…… s(i-1） s(i) …………. 匹配串：p⑴ p(j-1） p(j) 由此，我们得到关系式： ‘p⑴ p⑵ p⑶…..p(j-1）’ = ’ s(i-j+1）……s(i-1）’

20 由于s(i）≠p(j），接下来s(i）将与p(k）继续比较，则模式串中的前（k-1）个字符的子串必须满足下列关系式，并且不可能存在 k’>k 满足下列关系式：（k<j), ‘p⑴ p⑵ p⑶…..p(k-1）’ = ’ s(i-k+1）s(i-k+2）……s(i-1）’ 即： 主串：s⑴……s(i-k +1） s(i-k +2） ……s(i-1） s(i) …………. || （相配） || ||（有待比较） 匹配串：p⑴ p⑵ ……..... p(k-1） p(k)

21 现在我们把前面总结的关系综合一下 有： s⑴…s(i-j +1）… s(i-k +1） s(i-k +2） …… s(i-1） s(i) …… || （相配） || || || ≠（失配） p⑴ ……p(j-k+1） p(j-k+2） … p(j-1） p(j) || （相配） || ||（有待比较） p⑴ p⑵ …… p(k-1） p(k) 由上，我们得到关系： 'p⑴ p⑵ p⑶…..p(k-1）’ = ' p(j-k+1）p(j-k+2）……p(j-1）’

22 现在结合这上面的图模拟一下KMP算法的整个流程： 将S串和M串从第一个字符开始匹配； 如果匹配成功，则subM即灰色部分增加； 如果不成功，则M向后滑动使滑动后的subM的前缀和滑动前的subM的后缀重合，再进行匹配，如果还不成功，则再次滑动M，直到匹配成功或者M滑动到X处。如果到了X处，则从M串的起始位置进行匹配。

23 从上面的步骤可以知道，KMP的关键就是要知道当S串中的字符和M串中的字符不匹配时，S串要和M串中的哪个字符继续进行匹配。 KMP是通过定义了一个next数组，这个next数组保存了如果S中的字符和M中的字符不匹配时S要和M中的哪个字符重新进行匹配的坐标值。如图中所示的例子，S中的X位置和M不匹配了，那么S要和M中A段后面的字符进行比较，从图中来看是M向后滑动了。

24 换句话说，next[i]总是保存了当M[i]不匹配时要从M[next[i]]处进行匹配，这个M[next[i]]可能会匹配，如果还不匹配？那么可能会在M[next[next[i]]]处匹配了。 这里同时隐含着一个信息，就是i之前的一段字符和next[i]之前的一段字符是相同的，也就是M[0…i-1]相等的前缀和后缀。

25 现在考虑next[0],next[1]…next[i]都已经知道了，那么图示如下：
设j=next[i]，灰色部分表明这两段字符是相等的，如果i位置的字符和j位置的字符相等，那么next[i+1]=j+1; 因为前一段灰色部分和j位置的字符组成的字符串和后一段灰色的与i连接所形成的字符串是相等的。这正是前面对next数组的定义。 如果不相等，则要找到从i开始包括i往前的一段字符串与从0开始的一段字符串相等，这样形成相等的前缀和后缀。

26 所幸我们知道next[next[i]]的值，因为next[i]前面的字串也有最长的公共前缀和后缀，而这个公共的前缀与现在i以及往前形成的字串可能相等，这样一直向前找，如果找不到，则说明i位置的字符从来没有在之前出现过。 这样求出来的next数组其实是从下标1开始的，因为下标0之前是个空串，下标1则对应着M串的第0个字符。我们设next[0]=-1，仅仅是个标志而已，没有什么特殊的含义。

27 那么根据前面所述，可以很容易的写出初始化next数组的代码：
while(j < str.length() - 1){ if(str.charAt(j) == str.charAt(k)){ next[j + 1] = k + 1 ; j ++ ; k ++ ; } else if(k == 0){ next[j + 1] = 0 ; else k = next[k]; return next ; private int[] getNext(MyString str){ //求模式串str的next[j]函数值并用数组返回 int j = 1,k = 0 ; int[] next = new int[str.length()]; next[0] = -1 ; next[1] = 0 ;

28 我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示：
下标i 1 2 3 4 5 6 7 8 9 p(i) a b c d next[i] -1

29 下标i 1 2 3 4 5 6 7 8 9 p(i) a b c d next[i] -1

30 public int indexOf_KMPA(MyString subStr,int start){ //查找当前对象（即主串）中从start始的子串subStr //找到到则返回子串subStr在主串的开始字符下标，否则返回-1 int[] next = getNext(subStr); //求子串subStr的next[j]值 int i = start,j = 0,v; while(i < this.length() && j < subStr.length()){ if(j == -1 || this.charAt(i) == subStr.charAt(j)){ i ++ ; j ++ ; } else j = next[j]; } if(j == subStr.length()) v = i - subStr.length(); else v = -1; return v;