串的应用很广泛
案例：病毒感染检测（字符串序列——环装）
串的类型定义、存储结构及其运算
数据对象，数据关系，
基本操作：
StrAssign(&T， chars)
StrCompare(S, T)
StrLength(S)
★ Index(S, T, pos)
逻辑结构（线性）、存储结构（顺序串、链串）
串的顺序存储结构
#indefine MAXLEN 255
typedef struct{
char ch[MAXLEN + 1];
int length;
}SString;
串的链式存储结构
（多个字符放在一个结点，会提高存储密度 —— 块链）
在实际当中，顺序存储结构用的更多。（实际当中插入删除很少，匹配查找用顺序存储结构更加方便）
串的操作
（串的模式匹配算法）
目的：确定子串第一次出现的位置（定位）（没有就返回0）
应用：搜索引擎、拼写检查、语言翻译、数据压缩
BF（Brute-Force, 暴力破解）
KMP算法（特点：速度快）
BF
简单匹配法
正文串、模式
算法的思路是从S的每一个字符开始依次与T的字符进行匹配。
目标串、模式串
n=6, m=4
i = 1, j = 1;
匹配失败就：
i = i - j + 2; （目标串向前移动一下）
j = 1;（模式串从头开始）
匹配成功
返回：i - t.length
算法设计思想
将主串的第pos个字符和模式串的第一个字符比较，
若相等，继续逐个比较后续字符；
若不等，从主串的下一字符起，重新与模式串的第一个字符比较。
直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值0
从第一个位置开始查：i = 1
int Index_BF(SString S, SString T) {
int i = 1, j = 1;
while (i <= S.length && j <= T.length) {//循环条件
if (s.ch[i] == t.ch[j]) {
++i;
++j;
}
else {
i = i - j + 2;
j = 1;
}
}
if (j >= T.length)
return i - T.length;
else
return 0;
} 算法复杂度：
O（n*m）
KMP算法：（由三个科学家名字命名的）
利用已经部分匹配的结果而加快模式串的滑动速度
且主串S的指针i不必回溯，可以提速到O（n+m）
京公网安备 11010502036488号