串、串的模式匹配算法（子串查找）BF算法、KMP算法

串的定长顺序存储
#define MAXSTRLEN 255,//超出这个长度则超出部分被舍去，称为截断

串的模式匹配：

串的定义：0个或多个字符组成的有限序列
S = 'a1a2a3…….an '
n = 0时为空串
串的顺序存储结构：字符数组，串的长度就是数组末尾‘'前面的字符个数
数组需在定义时确定长度，有局限性
数组的最大长度
二：串的堆分配存储表示
typedef struct {
char *ch;
//若是非空串，则按串长分配存储区
//否则ch为空
int length; //串长度
}HString;
系统利用函数mallloc和free进行串值空间的动态分配，由此产生的新串
其实是系统先为新生成的串分配一个存储空间，然后进行串的复制（这是C语言的串类型
的存储方式）

三、串的块链存储方式

 1 #define CHUNKSIZE 80
 2 typedef struct Chunk{    //结点结构
 3 char ch[CHUNKSIZE];
 4 struct Chunk* next;
 5 }Chunk;
 6 
 7 typedef struct {    //串的链表结构
 8 Chunk*head, *tail;    //串的头和尾指针
 9 int curlen;    //串的当前长度
10 }LString;

data | 指针
1byte 4byte
1/5存储密度

4.3串的模式匹配算法（子串查找）
BF算法：朴素算法

 1 int Index(SString S, SString T, int pos)
 2 {
 3 i = pos; j = 1;
 4 while(i <= s[0] && j <= T[0])
 5 {
 6 if(s[i] == T[j])
 7 {
 8 ++i;
 9 ++j;
10 }
11 else    
12 {
13 i = i - j + 2;    //i指针回溯
14 j = 1;    //指针后退重新开始匹配
15 }
16 if(j > T[0])
17 return i - T[0];
18 else
19 return 0;
20 }
21 }

 1 int Index(SString S, SString T, int pos)
 2 {
 3 for(i = pos; i <= S[0] - T[0]; i++)
 4 {
 5 int k = i;
 6 for(j = 1; j <= T[0]; j++)
 7 {
 8 if（S[i] == T[j]）
 9 {
10 i++;
11 j++;
12 }
13 else
14 {
15 i = k;
16 break;
17 }
18 }
19 if(j > T[0])
20 return i - T[0];
21 else
22 return 0;
23 }
24 }

二、首尾匹配算法
先比较模式串的第一个字符
再比较模式串的最后一个字符
最后比较比较模式串中第二个得到倒数第二个之间的字符
算法复杂度和第一种一样O((n-m+1)m)

三、KMP算法
时间复杂度可达到O(m+n)

 1 int Index(SString S, SString T, int pos)
 2 {
 3 i = pos; j = 1;
 4 while(i <= s[0] && j <= T[0])
 5 {    
 6 //j == 0说明上次比较时第一个字符就不等next[1] = 0
 7 if(j == 0 || s[i] == T[j])
 8 {
 9 ++i;
10 ++j;
11 }
12 else    
13 {
14 j = next[j];    //i不用指针回溯
15 //j指针后退到next[j]重新开始匹配
16 }
17 }
18 if(j > T[0])
19 return i - T[0];
20 else
21 return 0;
22 
23 }

求next函数值
已知：next[1] = 0;
假设：next[j] = k; 又因为T[k] = T[j]
则next[j+ 1] = k + 1;
ruo T[j] != T[k]
则需要回朔，检查T[j] = T[?]
这是几上也是一个匹配过程，不同在于：主串和模式串是同一个串

 1 void get_next(SString &T, int &next[])//求模式串T的next函数值并存入数组next
 2 {
 3 i = 1; next[1] = 0;
 4 j = 0;
 5 while(i < T[0])
 6 {
 7 if(j == 0 || T[i] = T[j])
 8 {
 9 ++i;
10 ++j;
11 next[i] = j;
12 }
13 
14 else
15 j = next[j];
16 if(
17 }
18 
19 }

特殊情况
S = ‘aaabaaabaaabaaabaaab'
T = 'aaaab'
next[j] = 01234修正后00004

 1 void get_next(SString &T, int &next[])//求模式串T的next函数值并存入数组next
 2 {
 3 i = 1; next[1] = 0;
 4 j = 0;
 5 while(i < T[0])
 6 {
 7 if(j == 0 || T[i] = T[j])
 8 {
 9 ++i;
10 ++j;
11 if(T[i] != T[j])
12 nextval [i] = j;
13 else
14 nextval[i] = next[j];
15 }
16 
17 else
18 j = nextval[j];
19 if(
20 }
21 
22 }