改进办法3
每当一趟匹配过程中出现字符不相等时， 不回溯 j 指针，而是利用已经得到的部分 匹配结果将模式向右滑动一段距离。 j=2
j=6
ababcabcacbab abcac
i=4
ababcabcacbab
abc
ababcabcacbab abcac i=5
j=10
i=2
子串：a b c a c
next函数
s3 s2 s1
char s1[12] ="Hello world"; char s2[8]="2009"; char s3[6]="";
H
0
e
1
l
2
l
3
0
4 5
w
6
o
d \0
10 11
2
0
0
1
0
2
9
3
\0
4 5 6 7
\0
0 1 2 3 4 5
4.2.2 字符串类String的存储结构
String类支持字符串的动态变化。 namespace std { template <class charT, class traits = char_traits <charT>, class Allocator = alocator <charT>> class basic_string { public: ...... 有关字符串的属性 } 都封装在String中 } typedef basic_string <char> String;
时间复杂度
设主串T长度为n，子串P长度为m 最坏情况: 每次比较到P串的第m个字符时不匹 配，则时间复杂度为O(n*m)。
3
改进办法1
如果重新比较时，T中所剩的字符个数 不足子串P时，立即让算法终止。
改进办法2
每次先用子串的第一个字符及最 后一个字符与主串对应的字符进
j
行比较，若均相等，再比较中间 的字符。
1
4.1.3 字符串抽象数据类型
class string { string append(const char c); private: string concatenate(const char* s); ......; public: string copy(const char* s); string(); string insert(const char c, const int index); string(char* s); ~string(); int find(const char c, const int start); int length(); string substr(const int s, const int len); int isEmpty(); void clear(); };
4.3 字符串的模式匹配 主串：s=“babcabcacbab” 模式：t=“bcac”
Index(s,t) = 5
int NaiveStrMatching(const String& T,const String& P) { int i = 0, j = 0; int pLen = P.length(); P.length(); //模式长度 int tLen = T.length(); T.length(); //主串长度 if (tLen (tLen < pLen) pLen) return -1; while (i < pLen && j < tLen) tLen) { if (T[j ] == P[i]) (T[j] P[i]) { i++; j++; } else { j = j – i + 1; 0 1 2 3 4 5 6 7 8 i = 0; * * * * * * * * * } # # # } if (i >= pLen) pLen) return j – pLen +1; +1; else return -1; }
第4章
字符串
4.1 字符串的基本概念
4.1.1 字符编码 4.1.2 字符的编码顺序 4.1.3 字符串抽象数据类型
4.1 字符串的基本概念 4.2 字符串的存储结构和实现 4.3 字符串的模式匹配
与线性表的区别：
字符串:由0个或多个字符的顺序排列所组成 的复合数据结构，简称“串”。 串的长度：一个字符串所包含的字符个数。 空串：不含任何字符的字符串,长度为零。 字符串的数据元素约束为字符 线性表的基本操作通常以“单个元素” 作为操作对象，而字符串的基本操作 通常以“串整体”作为操作对象
String::String(char *s) { size = strlen(s); str = new char[size + 1]; assert( str != NULL); strcpy(str, s); }
String String::substr(int pos, int n) { int i; int left = size – pos; //查看剩余长度 String tmp; char *p, *q; if (pos>=size) return NULL; if (n>left) n = left; tmp.str = new char[n+1]; assert(tmp.str != NULL); p = tmp.str; q = &str[pos]; for (i = 0; i < n; i++) *p++ = *q++; *p = '\0'; tmp.size = n; return tmp; }
C++字符串的操作列表
substr( ) swap( ) copy( ) assign( ) = insert( ) += append( ) + find( ) replace( ) clear( ) size( ) length( ) max_size( ) 返回一个字符串的子串 交换两个字符串的内容 复制字符串 将一个字符串赋给另外一个字符串 与assign() 将一个字符或字符串插入到给定位置 将一个字符或字符串追加在另一个字符串后 将一个字符或字符串追加在另一个字符串后 将一个字符串连接在另一个字符串之后 查找并返回子序列的开始位置 替换字符或字符串 清空字符串 返回字符串中的字符个数 返回字符串长度 返回字符串允许的最大长度
4.1.1 字符编码
字符(char) ：组成字符串的基本单位。 在C/C＋＋中，字符采用 单字节（8 bits）表示 ASCII码对128个符号进行编码
4.1.2 字符的编码顺序
为了便于字符串的比较和运算，字符 编码表一般遵循约定俗成的“偏序编 码规则”。 字符偏序：根据字符的自然含义，某 些字符间具有一定的次序，在大多数 情况下就是字典序。
尽管时间复杂度为O(m*n), 但接近O(m+n)。
i: 0 1 2 3 4 5 6 7
模式串: next(i) :
abaabcac
-1 0 0 1 1 2 0 1
本章作业
习题
5,6,8
5
2
4.2.3 字符串运算的实现
int strcmp(const char *s1, const char *s2) { int i=0; while (s1[i] !='\0' &&s2[i]!='\0') { if (s1[i]>s2[i]) return 1; else if (s1[i]<s2[i]) return -1; i++; } if (s1[i]=='\0' && s2[i]!='\0') return -1; else if (s2[i]=='\0' && s1[i]!='\0') return 1; return 0; }
4.2 字符串的存储结构和实现
字符串的顺序存储 字符串类class String的存储结构
4.2.1
字符串的顺序存储
如果串长变化不大，可以有三种处理方案： （1）用S[0]作为记录串长的存储单元。 缺点：限制了串的最大长度不能超过256。 （2）为存储串的长度，另辟一个存储的地方。 缺点：串的最大长度是静态的，而不是动态的。 （3）用一个特殊的末尾标记'\0'。 例如：C/C++语言采用这种方法。
当模式串中第i个字符与主串中相应字 符不相等时，在模式中需用第几个 字符与主串的该字符(第j个字符)比较。
next函数
-1， next[i]=
当i=0时
Max{k|0<k<i且 p0..pk-1==p i-k...p i-1} 该集合不空 0 其它
4
int KMPStrMatching(const String &T,const String &P,int *N) { int i=0, j=0; int pLen=P.length(); //模式长度 int tLen=T.length(); //主串长度 if (tLen<pLen) return -1; while (i<pLen&&j<tLen){ if (i==-1||P[i]==T[j]) {i++;j++;} else i=N[i]; } if (i>=pLen]) return (j-pLen+1); else return -1; }
