串的定长顺序存储
#define MAXSTRLEN 255,//超出这个长度则超出部分被舍去，称为截断
串的模式匹配：
串的定义：0个或多个字符组成的有限序列
S = 'a1a2a3…….an '
n = 0时为空串
串的顺序存储结构：字符数组，串的长度就是数组末尾‘\0'前面的字符个数
数组需在定义时确定长度，有局限性
数组的最大长度
二：串的堆分配存储表示
typedef struct {
char *ch;
//若是非空串，则按串长分配存储区
//否则ch为空
int length; //串长度
}HString;
系统利用函数mallloc和free进行串值空间的动态分配，由此产生的新串
其实是系统先为新生成的串分配一个存储空间，然后进行串的复制（这是C语言的串类型
的存储方式）
三、串的块链存储方式
#define CHUNKSIZE 80
typedef struct Chunk{ //结点结构
char ch[CHUNKSIZE];
struct Chunk* next;
}Chunk; typedef struct { //串的链表结构
Chunk*head, *tail; //串的头和尾指针
int curlen; //串的当前长度
}LString;
data | 指针
1byte 4byte
1/5存储密度
4.3串的模式匹配算法（子串查找）
BF算法：朴素算法
int Index(SString S, SString T, int pos)
{
i = pos; j = ;
while(i <= s[] && j <= T[])
{
if(s[i] == T[j])
{
++i;
++j;
}
else
{
i = i - j + ; //i指针回溯
j = ; //指针后退重新开始匹配
}
if(j > T[])
return i - T[];
else
return ;
}
}
int Index(SString S, SString T, int pos)
{
for(i = pos; i <= S[] - T[]; i++)
{
int k = i;
for(j = ; j <= T[]; j++)
{
if（S[i] == T[j]）
{
i++;
j++;
}
else
{
i = k;
break;
}
}
if(j > T[])
return i - T[];
else
return ;
}
}
二、首尾匹配算法
先比较模式串的第一个字符
再比较模式串的最后一个字符
最后比较比较模式串中第二个得到倒数第二个之间的字符
算法复杂度和第一种一样O((n-m+1)m)
三、KMP算法
时间复杂度可达到O(m+n)
int Index(SString S, SString T, int pos)
{
i = pos; j = ;
while(i <= s[] && j <= T[])
{
//j == 0说明上次比较时第一个字符就不等next[1] = 0
if(j == || s[i] == T[j])
{
++i;
++j;
}
else
{
j = next[j]; //i不用指针回溯
//j指针后退到next[j]重新开始匹配
}
}
if(j > T[])
return i - T[];
else
return ; }
求next函数值
已知：next[1] = 0;
假设：next[j] = k; 又因为T[k] = T[j]
则next[j+ 1] = k + 1;
ruo T[j] != T[k]
则需要回朔，检查T[j] = T[?]
这是几上也是一个匹配过程，不同在于：主串和模式串是同一个串
void get_next(SString &T, int &next[])//求模式串T的next函数值并存入数组next
{
i = ; next[] = ;
j = ;
while(i < T[])
{
if(j == || T[i] = T[j])
{
++i;
++j;
next[i] = j;
} else
j = next[j];
if(
} }
特殊情况
S = ‘aaabaaabaaabaaabaaab'
T = 'aaaab'
next[j] = 01234修正后00004
void get_next(SString &T, int &next[])//求模式串T的next函数值并存入数组next
{
i = ; next[] = ;
j = ;
while(i < T[])
{
if(j == || T[i] = T[j])
{
++i;
++j;
if(T[i] != T[j])
nextval [i] = j;
else
nextval[i] = next[j];
} else
j = nextval[j];
if(
} }