目录
串的概念
串（String）——由零个或多个任意字符组成的有限序列。
空串用?表示。
概念
子串：串中任意个连续字符组成的子序列称为该串的子串。
主串：包含子串的串相应地称为主串。
字符位置：字符在序列中的序号为该字符在串中的位置。
子串位置：子串第一个字符在主串中的位置。
空格串：由一个或多个空格组成的串，与空串不同。
实例
字符串a、b、c、d
a='BEI'
b='JING'
c='BEIJING'
d='BEI JING'
它们的长度分别是：3、4、7、8
c的子串是：a、b
d的子串是：a、b
a在c中的位置是：1
a在d中的位置是：1
b在c中的位置是：4
a在d中的位置是：5
串相等
当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。
如："abcd"?≠ "abc"
所有空串是相等的。
串的类型定义与存储结构
类型定义
ADT String {
? ? ? ? 数据对象：D={ai | ai∈CharacterSet, i=1,2,...,n, n?≥ 0}
? ? ? ? 数据关系：R1={<ai-1,ai>|ai-1,ai∈D.i=1,2,...,n}
}
存储结构
串的顺序存储结构
#define MAXLEN 255
typedef struct{
char ch[MAXLEN+1]; // 存储串的一维数组
int length; // 串的当前长度
}SString;串的链式存储结构
?优点：操作方便
缺点：存储密度较低
存储密度=串值所占的存储/实际分配的存储。
解决其存储密度低的方案：可将多个字符存放在一个结点中。
// 串的链式存储结构——块链结构
#define CHUNKSIZE 80 // 块的大小可由用户定义
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
} Chunk;
typedef struct {
Chunk *head, *tail; // 串的头指针和尾指针
int curlen; // 串的当前长度
}LString; // 字符串的块链结构串的算法
算法目的：
? ? ? ? 确定主串中所含子串（模式串）第一次出现的位置（定位）。
算法应用：
? ? ? ? 搜索引擎、拼写检查、语言翻译、数据压缩
算法种类：
? ? ? ? ·?BF算法（Brute-Force，又称古典的、经典的、朴素的、穷举的）。
? ? ? ? ·?KMP算法（特点：速度快）
BF算法
算法步骤
① 分别利用计数指针 i 和 j 指示主串 S 和模式 T中当前正待比较的字符位置， i?初值为pos, j 初值为1。
② 如果两个串均未比较到串尾， 即 i 和 j 均分别小于等于S和T的长度时，则循环执行以下操作：
? S[i].ch和T[j].ch比较，若相等，则i和j分别指示串中下个位置， 继续比较后续字符；
? 若不等，指针后退重新开始匹配， 从主串的下一个字符 (i=i-j+2) 起再重新和模式的第一个字符 (j=1) 比较。
③ 如果j > T.length, 说明模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的序号(i-T.length); 否则称匹配不成功，返回0。
int Index_BF(SString S,SString T,int pos)
{ // 返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在， 则返回值为0
// 其中，T非空，1≤pos≤s.length
i=pos; j=l; //初始化
while (i <=S.length && j <=T.length) //两个串均未比较到串尾
{
if(S[i].ch==T[j].ch) {++i;++j;} //继续比较后继字符
else{i=i-j+2;j=l;} //指针后退重新开始匹配
}
if (j > T.length) return i-T.length; //匹配成功
else return 0; //匹配失败
}实例
S= "aaaaaba "
T= "ba"
?时间复杂度
例：S='0000000001'，T='0001'，pos=1
若n为主串长度，m为子串长度，最坏情况是：
·?主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次。
·?最后m位也各比较了1次。
总次数为：(n-m)*m+m = (n-m+1)*m
若m<<n，则算法复杂度O(n+m)
KMP算法
// KMP算法
int Index_KMP(SString S,SString T,int pos)
{ // 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置
// 其中，T非空， 1≤pos≤S.length
i=pos;j=l;
while (i <=S.length && j <=S.length) // 两个串均未比较到串尾
{
if (j == 0 || S[i]==T[j]) { ++ i; ++j ;} // 继续比较后继字符
else j=next[j]; // 模式串向右移动
}
if (j > T[0]) return i-T[0]; // 匹配成功
else return 0; // 匹配失败
}
// 计算 next 函数值
void get_next(SString T,int next[])
{ //求模式串 T的 next 函数值并存入数组 next
i=1;next[l]=0;j=0;
while (i <T[0])
{
if(j=0 || T[i]==T[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}// 计算 next 函数修正值
void get_nextval(SString T, int nextval[])
{ // 求模式串 T 的 next 函数修正值并存入数组 nextval
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];
}
}
?
?
