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

串的定长顺序存储
#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(

 }

 }

巴特西

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

最新文章

热门文章