4.1 定义
- 一种特殊的线性表
4.2 串的存储结构
顺序存储
1
2
3
4
5
6
7
8
9
10
typedef struct{
char ch[MAXLEN]; //静态数组
int length;
} SString;
typedef struct{
char *ch; //动态数组
int length;
} HString;链式存储
1 | //2. 链式存储 |
4.3 基本操作
函数名 | 功能 | 时间复杂度 |
---|---|---|
StrAssign(SString &T, char *chars) | 生成一个其值等于chars的串T | O(n) |
StrCopy(SString &T, SString S) | 由串S复制得串T | O(n) |
StrEmpty(SString S) | 若S为空串,则返回true,否则返回false | O(1) |
StrLength(SString S) | 返回串S的元素个数,即串的长度 | O(1) |
ClearString(SString &S) | 将串S清为空串 | O(1) |
DestroyString(SString &S) | 串S存在,则销毁它 | O(1) |
Concat(SString &T, SString S1, SString S2) | 用T返回由S1和S2联接而成的新串 | O(n) |
1 | //求子串 |
4.4 模式匹配
4.4.1 朴素模式匹配算法
1 | //朴素模式匹配算法 |
4.4.2 KMP模式匹配算法
- 1)根据模式求next数组
- 算法优化
next[3]=1 , next[3]与next[1]相等,所以转到next[1]后也会失配,所以next[3]可以改为next[1]=0
1 | //KMP算法 |