第四章串 4.1 串类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例.

Presentation on theme: "第四章串 4.1 串类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例."— Presentation transcript:

1 第四章串 4.1 串类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例

2 4.1 串类型的定义 串是由零个或多个字符组成的有限序列 一般记作：S= a1a2…an 其中S是串名， 单引号括起来的字符序列是串的值 N为串长度，零个字符的串为空串 串中任意个连续字符构成的子序列为子串 字符在序列中的序号为串的位置

3 例如：a= BEI b= BEIJING c= JING d=  e=   a的长度为3，c是b的子串， c在b中的位置为4 注意串一般由单引号括起来表示， 区别于C语言中用双引号括起来表示字符串 在利用C语言实现时注意编程时语句格式

4 例如：a= BEI b= BEIJING c= JING d=  e=   注意空串和空格串 由一个或多个空格构成的串为空格串 两个单引号中间无任何字符时表示空串 一般用Ф表示 空串是任意串的子串

5 基本操作： StrAssign (&T, chars) DestroyString(&S) StrLength(S) StrCopy (&T, S) Concat (&T, S1, S2) StrCompare (S, T) StrEmpty (S) ClearString (&S) SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len)

6 StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。 DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。

7 StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。
  表示空串，空串的长度为零。

8 例如：StrCompare(data, state) < 0 StrCompare(cat, case) > 0
StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S  T，则返回值  0； 若S  T，则返回值  0； 若S  T，则返回值  0。 例如：StrCompare(data, state) < 0 StrCompare(cat, case) > 0

9 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数，称为串的长度。
Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S 联接而成的新串。 例如： Concate( T, man, kind) 求得 T = mankind

10 SubString (&Sub, S, pos, len)
初始条件：串 S 存在，1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。 SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9) 求得 sub = commander； SubString( sub, commander, 9, 1) 求得 sub = r；

11 SubString (&Sub, S, pos, len)
初始条件：串 S 存在，1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。 SubString( sub, commander, 4, 0) 求得 sub =  ；

12 Index (S, T, pos) 初始条件：串S和T存在，T是非空串， ≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。 假设 S = abcaabcaaabc, T = bca 2 Index(S, T, 1) Index(S, T, 3) 6 Index(S, T, 8)

13 StrInsert (&S, pos, T) 初始条件：串S和T存在，
1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前 插入串T。 例如：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character

14 StrDelete (&S, pos, len) 初始条件：串S存在
1≤pos≤StrLength(S)-len+1。 操作结果：从串S中删除第pos个字符 起长度为len的子串。 ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串。

15 strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数；
对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 例如：C语言函数库中提供下列串处理函数： gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数；

16 串操作定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。

17 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。
Index (S, T, pos) 初始条件：串S和T存在，T是非空串， ≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。

18 ? i 算法的基本思想为： 从pos位置开始在S中取子串 X = SubString(S, i, StrLength(T)),
StrCompare( X , T ) i S 串 pos n-m+1 T 串 T 串 若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0

19 int Index (String S, String T, int pos) {
} return 0; if (pos <= 0) return ERROR; n = StrLength(S); m = StrLength(T); i = pos; while ( i <= n-m+1) { } SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) ++i ; else return i ;

20 作业 实现串的替换操作，replace函数

21 串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。

22 4.2 串的表示和实现 一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示

23 一、串的定长顺序存储表示 用一组连续的预定义大小的内存单元中存储字符串序列，串的长度须在预定义长度范围内，超出预定义长度则超出部分被舍弃，称为截断 表示串长度时有两种方式： 一种是将串长度存入下标为0的单元中 另外一种是在串的末尾加上’\0’结束标志 此时串长度是隐含的

24 下面给出串的定义形式 #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring[MAXSTRLEN + 1]; 如此定义后Sstring为串类型 Sstring s；表示s中最多可存储255个字符， 其中s[ 0]单元存放串的长度

25 语句形式 T[ 1..S1[0] ] = S1[1..S1[0]]; S1[0]中存放字符串长度 作用：将s1中的字符串复制给t

26 下面以串连接和求子串函数的实现说明串的使用
假设S1和S2是Sstring类型变量 串T由S1串连接S2得到 实现方法： 将S1复制到T的前半段，然后将S2复制到T的后半段，若超出最大长度则进行截断

27 Status Concat(SString S1, SString S2, SString &T) {
return uncut; } // Concat if (S1[0]+S2[0] <= MAXSTRLEN) { T[ 1..S1[0] ] = S1[1..S1[0]]; T[ S1[0]+1..S1[0]+S2[0] ] = S2[ 1.. S2[0] ]; T[0] = S1[0]+S2[0] ; uncut = FALSE; }

28 Status Concat(SString S1, SString S2, SString &T) {
return uncut; } // Concat if (S1[0]+S2[0] <= MAXSTRLEN) { … } else if (S1[0] <MAXSTRSIZE) { T[ 1..S1[0] ] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; }

29 Status Concat(SString S1, SString S2, SString &T) {
return uncut; } // Concat if (S1[0]+S2[0] <= MAXSTRLEN) { … } else if (S1[0] <MAXSTRSIZE) { else { T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; T[0] == S1[0] == MAXSTRLEN }

30 二、串的堆分配存储表示 串的顺序存储表示有何缺点 串的操作时可能会出现截断 当串长度小于存储区长度时会浪费内存空间 堆分配存储表示是利用malloc和free函数来管理一段称为“堆”的内存区域，需要时则分配，使用完毕后则释放。 通过malloc分配的内存可以利用内存地址使用

31 typedef struct { char *ch; int length; } HString; HString S； B C D E F G H A I J S 10 S.ch = (char *) malloc (10 * sizeof(char) ) S.Length = 10;

32 串的连接操作： 假设有串S1和串S2连接成串T B C D E A S1 5 F G H I J S1 5 A B C D E F G H
10 特别注意：若T原来有内存则须先释放原有内存

33 Status Concat(HString &T, HString S1, HString S2)
{ if ( T.ch ) free(T.ch); T.ch = (char*) malloc((S1.length+S2.length)*sizeof(char)); T.ch[0..S1.length-1] = S1.ch[0..S1.length-1]; T.ch[S1.length..T.length-1] = S2.ch[0..S2.length-1]; T.length = S1.length + S2.length; return OK; }

34 Status StrAssign(HString &T,char *chars){
串的其他操作函数 Status StrAssign(HString &T,char *chars){ } if ( T.ch ) free (T); for( i=0 , c= chars; c ; ++i, ++c;) ; if ( !i ) { T.ch=NULL ; T.length=0; } else { T.ch=(char*)malloc(i*sizeof(char)); T.ch[0..i-1]= chars[0..i-1]; T.length=i; } 产生一个串T，内容为chars所指字符串

35 L L 三、串的块链存储表示 B A E ^ C D 存储密度 = 数据元素所占存储位 实际分配的存储位 C A B D E F G H I

36 #define CHUNKSIZE 80 // 可由用户定义块大小
typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;

37 实际应用时， 可以根据问题所需来设置结点的大小。 例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。

38 4.3 串的模式匹配算法 这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。

39 首先，回忆一下串匹配(查找)的定义: INDEX (S, T, pos) 初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。 操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中第pos个字符之后第一次出现的位置；否则函数 值为0。

40 以定长顺序结构表示串时的算法。 一、简单算法 二、KMP算法

41 串的匹配算法 B A C \0 B A C \0

42 B A C \0 B A C \0

43 B A C \0 B A C \0

44 B A C \0 B A C \0

45 B A C \0 B A C \0

46 S[0]中存放S串的长度 一、简单算法 int Index(SString S, SString T, int pos) { i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if ( S[i] == T[j] ) { ++i; ++j; } else { i = (i-j+1)+1; j = 1; } } if (j > T[0]) return i-T[0]; else return 0;

47 二、KMP 算法 第一趟比较 a b a b c a b c a c b a b i=1 a b c a c j=1

48 二、KMP 算法 第一趟比较 a b a b c a b c a c b a b i=2 a b c a c j=2

49 二、KMP 算法 第一趟比较 a b a b c a b c a c b a b i=3 a b c a c j=3 当比较发现模式中的第j字符与主串中的第i个字符不相等时，再次比较时不从头开始，而是让模式串向右滑动，再次进行比较

50 二、KMP 算法 第二趟比较 a b c i=3 a b c j=1 当比较发现模式中的第j字符与主串中的第i个字符不相等时，再次比较时不从头开始，而是让模式串向右滑动，再次进行比较。 滑动多少个字符？这是关键问题

51 二、KMP 算法 第二趟比较 a b c i=4 a b c j=2

52 二、KMP 算法 第二趟比较 a b c i=5 a b c j=3

53 二、KMP 算法 第二趟比较 a b c i=6 a b c j=4

54 二、KMP 算法 第二趟比较 a b c i=7 a b c j=5 当比较发现模式中的第j字符与主串中的第i个字符不相等时，再次比较时不从头开始，而是让模式串向右滑动，再次进行比较。 滑动多少个字符？这是关键问题

55 二、KMP 算法 第三趟比较 a b c i=7 a b c j=2 当比较发现模式中的第j字符与主串中的第i个字符不相等时，再次比较时不从头开始，而是让模式串向右滑动，再次进行比较。 滑动多少个字符？这是关键问题

56 二、KMP 算法 第三趟比较 a b c i=8 a b c j=3

57 二、KMP 算法 第三趟比较 a b c i=9 a b c j=4

58 二、KMP 算法 第三趟比较 i=10 j=5 匹配成功 关键问题： 当主串第i字符与模式中的第j字符不匹配时
a b c i=10 a b c j=5 匹配成功 关键问题： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的哪个字符进行下一步比较

59 二、KMP 算法 i=7 j=5 关键问题： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的哪个字符进行下一步比较 a b
c i=7 a b c j=5 关键问题： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的哪个字符进行下一步比较

60 二、KMP 算法 i=7 j=5 假设： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的第k字符进行下一步比较
a b c i=7 a b c j=5 假设： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的第k字符进行下一步比较 此时k值取多少？

61 二、KMP 算法 i=7 j=5 假设： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的第k字符进行下一步比较 a b c

62 二、KMP 算法 i=7 j=5 第k字符 k=2 假设： 当主串第i字符与模式中的第j字符不匹配时
a b c i=7 a b c j=5 第k字符 k=2 假设： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的第k字符进行下一步比较 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始与第i字符再次比较

63 假设： 当主串第i字符与模式中的第j字符不匹配时 第i字符应与模式中的第k字符进行下一步比较 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较 next[1]= 0 next[2]= 1 next[3]=？ … next[j]=？

64 第k字符前的k-1个字符与第j字符前的k-1个字符相等
a b c i=7 a b c j=5 a b c i=7 a b c j=5 第k字符 k=2 得到结论： 第k字符前的k-1个字符与第j字符前的k-1个字符相等

65 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。
另一个模式匹配的例子 a b c c a b c 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。

66 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。
另一个模式匹配的例子 a b c a c a b c 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。 此时为什么k值取为3？

67 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。
另一个模式匹配的例子 a b c a a c a b c 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。 此时为什么k值取为3？

68 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。
另一个模式匹配的例子 a b c a a c a b c 主串中的第i个字符与模式中的第j个字符不相等时，将模式串向右滑动，使得第i字符与模式中的第k字符进行下一次比较。 此时为什么k值取为3？

69 第k字符前的k-1个字符与第j字符前的k-1个字符相等
a b c c a b c i a b c c a b c j k 第k字符前的k-1个字符与第j字符前的k-1个字符相等 令next[j]=k 表示第j个字符与第i个字符不相等时使第i字符与第k字符进行下一次比较

70 第k字符前的k-1个字符与第j字符前的k-1个字符相等 若第k个字符与第j个字符相等，则next[j+1]值为k+1
next[j]=k 表示当第j字符与第i字符不匹配时应该从模式中的第k字符开始与第i字符再次比较， next[j+1]如何计算？ …………… ………………… 模式 j j+1 k-1 k k-1 k k 第k字符前的k-1个字符与第j字符前的k-1个字符相等 若第k个字符与第j个字符相等，则next[j+1]值为k+1 next[j+1] = next[j]+1 推导出：next[j+1] =？？

71 若不存在k’，则 next[j+1] =1 k j j+1 …………… ……………… k’ k’
…………… ……………… k’ k’+1 k’ 第k字符前的k-1个字符与第j字符前的k-1个字符相等 若第k个字符与第j个字符不相等， next[j+1] = k’+1 若不存在k’，则 next[j+1] =1

72 规定Next[1] = 0 表示模式中第1个字符与主串第i字符不相等时，无需j值回退，直接比较i+1字符即可
next[j]=k 表示当第j字符与第i字符不匹配时应该从模式中的第k字符开始与第i字符再次比较 规定Next[1] = 0 表示模式中第1个字符与主串第i字符不相等时，无需j值回退，直接比较i+1字符即可 当不存在 第j字符前的k-1个字符与 1到k-1 的字符序列相等时 表示j需要回退至模式的第一个字符 a b a a b c a c Next[j]

73 a b a b a a b a b Next[j]

74 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] ) { if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 1 1 2 3 4 5 6 7 8 j= a b a a b c a c Next[j]

75 1 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 2 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1

76 1 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 2 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1

77 1 1 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 3 2 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1 1

78 1 1 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 3 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1 1

79 1 1 2 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 4 1 2 3 4 5 6 7 8 j= 2 a b a a b c a c Next[j] 1 1 2

80 1 1 2 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 4 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1 1 2

81 1 1 2 2 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 5 1 2 3 4 5 6 7 8 j= 2 a b a a b c a c Next[j] 1 1 2 2

82 1 1 2 2 3 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 6 1 2 3 4 5 6 7 8 j= 3 a b a a b c a c Next[j] 1 1 2 2 3

83 1 1 2 2 3 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 6 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1 1 2 2 3

84 1 1 2 2 3 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 6 1 2 3 4 5 6 7 8 j= a b a a b c a c Next[j] 1 1 2 2 3

85 1 1 2 2 3 1 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 7 1 2 3 4 5 6 7 8 j= 1 a b a a b c a c Next[j] 1 1 2 2 3 1

86 1 1 2 2 3 1 2 Next的算法 i=1； nextval[1]=0; j=0; While ( i< T[0] )
{ if( j= =0 || T[i]= =T[j] ) { i++; j++; next[i] = j; else j = next[j]; } i= 8 1 2 3 4 5 6 7 8 j= 2 a b a a b c a c Next[j] 1 1 2 2 3 1 2

87 Next中存在的问题 a b i=1 a b j=1 a a a a b Next[j]

88 Next中存在的问题 a b i=4 a b j=4 a a a a b Next[j]

89 Next中存在的问题 a b i=4 a b j=3 a a a a b Next[j]

90 Next中存在的问题 a b i=4 a b j=2 a a a a b Next[j]

91 Next中存在的问题 a b i=4 a b j=1 a a a a b Next[j]

92 Next中存在的问题 a b i=5 a b j=1 a a a a b Next[j]

93 Next中存在的问题 a b i=9 a b j=5 a a a a b Next[j]

94 第j字符不匹配时，由于模式中第j字符前的字符一样，所以无需判断j之前的字符是否与主串的第i字符是否匹配 1 2 3 4 5
Next中存在的问题 a b i=9 a b j=5 第j字符不匹配时，由于模式中第j字符前的字符一样，所以无需判断j之前的字符是否与主串的第i字符是否匹配 a a a a b Next[j]

95 Next的修正算法 第j字符不匹配时，由于模式中第j字符前字符一样，所以无需判断j之前的字符是否与主串的第i字符是否匹配 i=1； nextval[1]=0; j=0; While ( i< T[0] ) { if( j==0 || T[i]==T[j] ) { i++; j++; if( T[i]!=T[j] ) nextval[i] = j; else nextval[i] = nextval[j]; } else j=nextval[j];

96 请详细了解KMP模式匹配算法中 next值得计算过程！

97 4.4 串操作的应用举例 本节内容作为课下作业 建立一个文件A内存常用词 另一个文件B存一篇文章的摘要 编写程序从文件B中读取内容并分析出哪些是关键词，输出显示出所有关键词

98 本章学习要点 1. 熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其上实现串操作的基本方法。

99 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较
c b a i= 2 1 a b c j= 1 1 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较 j=1时，规定next[1]的值为0 模式中的第1个字符与主串中的第i个字符不相等时，模式不滑动，主串i加1，模式中的j仍是1 其他next[j]如何求得？

100 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较
c b a i= 3 2 a b c j= 1 1 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较 j=1时，规定next[1]的值为0 模式中的第1个字符与主串中的第i个字符不相等时，模式不滑动，主串i加1，模式中的j仍是1 其他next[j]如何求得？

101 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较
c b a i= 4 3 a b c j= 2 1 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较 j=1时，规定next[1]的值为0 模式中的第1个字符与主串中的第i个字符不相等时，模式不滑动，主串i加1，模式中的j仍是1 其他next[j]如何求得？

102 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较
c b a i= 5 4 a b c j= 3 2 令 next[j]=k 表示当第j字符与第i字符不匹配时，应该从模式中的第k字符开始再次比较 j=1时，规定next[1]的值为0 模式中的第1个字符与主串中的第i个字符不相等时，模式不滑动，主串i加1，模式中的j仍是1 其他next[j]如何求得？