github中有详尽代码可作参考
返回目录
串的定长顺序存储表示
串的顺序存储结构是用一组地址连续的存储单元来存储字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般用定长数组来定义。
#define MaxLen 255
typedef struct {
char ch[MaxLen+1];
//存储串的一维数组,ch[0]~ch[255],共256个;
//通常情况下 ch[0]存放串的长度,或者闲置不用,真正串的内容从ch[1]开始
int length;
}SString;
串的堆分配存储
typedef struct{
char *ch;
int length;
}HString;
void InitHString(HString &Str)
{
Str.length=0;
Str.ch=(char *)malloc((MaxLen+1)*sizeof(char));
}
void DestroyString(HString &Str)//销毁操作
{
free(Str.ch);
}
串的块链存储
将多个字符存储在一个结点，那么这一个节点叫做一个存储块，即块链
#define MaxBlockSize 4
//不带头结点
typedef struct Chunk{
char ch[MaxBlockSize];
Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*rear;
int length;
}LString;
github中有详尽代码可作参考
n为主串长度, m为模式串长度,求模式匹配(子串或模式串在主串中的位置)
朴素模式匹配算法
时间复杂度为 O(nm)
int StrIndex(SString Str1,SString Str2)//定位操作
{
int pos1=1,pos2=1;//分别指向Str1和Str2的第一个元素
while(pos1<=Str1.length&&pos2<=Str2.length)
{
if(Str1.ch[pos1]==Str2.ch[pos2])
pos1++,pos2++;
else pos1=pos1-pos2+2,pos2=1;
}
if(pos2>Str2.length)
return pos1-Str2.length;
else return 0;
}
KMP算法
时间复杂度为 O(m+n),求 next数组时间复杂度为 O(m),模式匹配过程最坏时间复杂度为 O(n).
int StrIndex_KMP(SString Str1,SString Str2,int next[])//定位操作
{
int i=1,j=1;//分别指向Str1和Str2的第一个元素
while(i<=Str1.length&&j<=Str2.length)
{
if(j==0||Str1.ch[i]==Str2.ch[j])//j==0时也需要
i++,j++;
else j=next[j];
}
if(j>Str2.length)
return i-Str2.length;
else return 0;
}
计算next数组
手算思想: next[1]填 0; next[2]填 1;其他的 next,在不匹配的位置前,划一根分界线,模式串一步一步往后退,直到分界线之前能对上,或模式串完全跨过分界线为止.此时 j指向哪, next数组值就是多少.
//教材写法
void get_next(SString Str,int next[])
{
int i=1,j=0;
next[1]=0;
while(i<Str.length)
{
if(j==0||Str.ch[i]==Str.ch[j])
i++,j++,next[i]=j;
else j=next[j];//往前找
}
}
计算nextval数组
手算思想: 先求 next数组,再由 next数组求 nextval数组.当 s[next[j]]==s[j],则 nextval[j]=nextval[next[j]];反之, nextval[j]=next[j].
void get_next_val(SString Str,int next[],int nextval[])//可通过next数组直接求
{
nextval[1]=0;
for(int j=2;j<=Str.length;j++)
{
if(Str.ch[next[j]]==Str.ch[j])
nextval[j]=nextval[next[j]];
else nextval[j]=next[j];
}
}
//教材写法
void get_next_val(SString Str,int nextval[])
{
int i=1,j=0;
nextval[1]=0;
while(i<Str.length)
{
if(j==0||Str.ch[i]==Str.ch[j])
{
i++,j++;
if(Str.ch[i]!=Str.ch[j])
nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];//往前找
}
}
关于计算 next和 nextval可参考上面的手算思想
已知串 S=′aaab′，其 next数组值为().
A. 0123
B. 0112
C. 0231
D. 1211
教材做法
串 ′ababaaababaa′的 next数组值为().
A. 012345678999
B. 012121111212
C. 011234223456
D. 012301232234
串 ′ababaaababaa′的 next数组为().
A. −1,0,1,2,3,4,5,6,7,8,8,8
B. −1,0,1,0,1,0,0,0,0,1,0,1
C. −1,0,0,1,2,3,1,1,2,3,4,5
D. −1,0,1,2,−1,0,1,2,1,1,2,3
串 ′ababaaababaa′的 nextval数组为().
A. 0,1,0,1,1,2,0,1,0,1,0,2
B. 0,1,0,1,1,4,1,1,0,1,0,2
C. 0,1,0,1,0,4,2,1,0,1,0,4
D. 0,1,1,1,0,2,1,1,0,1,0,4
- 求 next数组
当求位序的 next数组,过程如上;当求下标的 next数组,无非在位序的 next数组基础上每个数 −1即可.
- 求 nextval数组
教材做法(忽略水印)
2015统考真题：已知字符串 S为 ′abaabaabacacaabaabcc′，模式串 t为 ′abaabc′.采用 KMP算法进行匹配，第一次出现“失配”( s[i]≠s[j])时， i=j=5，则下次开始匹配时， i和 j的值分别是().
A. i=1,j=0
B. i=5,j=0
C. i=5,j=2
D. i=6,j=2
注意题目中 i=j=5时失配,可发现是下标法(对应编号是 6),由表知 i不变, j变成对应的 next数组值,故 i=5, j=2
2019统考真题：设主串 T=′abaabaabcabaabc′，模式串 s = ‘abaabc’，采用 KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是().
A. 9
B. \color{Red}{10}
C. 12
D. 15
模式串同上题的一样.
下划线处表示比较的次数,共 6+4=10次.
4.2.1
在字符串模式匹配的 KMP算法中，求模式的 next数组值的定义如下:
1)当 j=1时,为什么要取 next [1]=0?
2)为什么要取
max{k}， k最大是多少?3)其他情况是什么情况，为什么取 next[j]=1?
1)当模式串中的第一个字符和主串的当前字符比较不相等时， next[1]=0，表示模式串应该右移一位，主串当前指针也要后移一位，再和模式串中的第一字符进行比较;
2)当主串的第 i个字符与模式串的第 j个字符失配时，主串 i不回溯，则假定模式串的第 k个字符与主串的第 i个字符比较， k值应满足条件 1 < k < j且 ’p_1 \cdots p_{k-1}’=’p_{j-k+1} \cdots p_{j-1}’，即 k为模式串的下次比较位置。 k值可能有多个，为了不使向右移动丢失可能的匹配，右移距离应该取最小，由于 j-k表示右移的距离，所以取 max{k}。
3)除上面两种情况外，发生失配时，主串指针 i不回溯，在最坏情况下，模式串从第 1个字符开始与主串的第 i个字符比较。
4.2.2
设有字符串 S= ‘aabaabaabaac’， P=’aabaac’.
1)求出 P的 next数组.
2)若 S作主串， P作模式串，试给出 KMP算法的匹配过程。
1)
2)
