子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置,又被称为串的模式匹配
//BF模式匹配算法
int Index(HString S, int pos, HString T) {
int i = pos;//主串从pos开始
int j = 1;//模式串从头开始
while (i <= S.len&&j <= T.len) {
if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
i++;
j++;
}
else {//当对应字符不相等时
i = i - j + 2;//主串回溯到i-j+2的位置重新比较
j = 1;//模式串从头开始重新比较
}
}
if (j > T.len) {//匹配成功时,返回匹配起始位置
return i - T.len;
}
else {//匹配失败,返回0
return 0;
}
}
由此可见,next函数的计算仅与模式串本身有关,和主串无关。其中’T1T2…T(k-1)'时’T1T2…T(j-1)'的真前缀子串, ‘T(j-k+1)T(j-k+2)…T(j-1)’是’T1T2…T(j-1)'的真后缀子串。当next函数定义中的集合不为空时,next[j]的值等于串’T1T2…T(j-1)'的真前缀子串和真后缀子串相等时的最大子串长度+1 通过以上分析,推导出模式串"abaabcac"的next值的计算过程如下表所示. (1).当j=1时,由定义得知,next[1]=0; (2)当j=2时,满足1<k<j的k值不存在,由定义得知next[2]=1;
则我们可以得出next值
void Get_Next(HString T, int next[]) {
int j = 1, k = 0;
next[1] = 0;
while (j < T.len) {
if (k == 0 || T.ch[j] == T.ch[k]) {
++j;
++k;
next[j] = k;
}
else {
k = next[k];
}
}
}
我们在前面介绍的next函数虽然好用,但还不够完美,在某种情况下是有缺陷的,例如如下匹配过程 主串为"aaabaaaab" 模式串为"aaaab"
在求得模式串的next值之后,匹配过程如下:
从串的匹配过程可以看到,当i=4,j=4时,S4!=T4,由next[j]所示还需进行i=4、j=3,i=4、j=2,i=4、j=1这三次比较。实际上,因为模式串中的第1、2、3个字符和第4个字符都相等(即都是’a’),因此,不需要再和主串中第4个字符相比较,而可以直接将模式串一次向右滑动4个字符的位置直接进行i=5、j=1的判断。 这就是说,若按上述定义得到next[j]=k,而模式串中T(j)!=T(k),则当Si != Tj时,不需要进行Si和Tk的比较,直接和Tnext[k]进行比较;换句话说,此时的next[j]的值应和next[k]相同,为此将next[j]修正为nextval[j]。而模式串中Tj !=Tk,则当Si !=Tj时,还是需要比较Si和Tk的比较,因此nextval[j]的值就是k,即nextval[j]得值就是next[j]的值。 通过以上分析,计算第j个字符得nextval值时,要看第j个字符是否和第j个字符的next值指向的字符相等。若相等,则nextval[j]=nextval[next[j]];否则,nextval[j]=next[j]。 由此推导出模式串T='aaaab’的nextval值的计算过程如下:
可以看到匹配次数大大减少,降低了复杂度。
void Get_Next(HString T, int next[]) {
int j = 1, k = 0;
next[1] = 0;
while (j < T.len) {
if (k == 0 || T.ch[j] == T.ch[k]) {
++j;
++k;
next[j] = k;
}
else {
k = next[k];
}
}
}
void Get_NextVal(HString T, int next[], int nextval[]) {
int j = 2, k = 0;
Get_Next(T, next);
nextval[1] = 0;
while (j <= T.len) {
k = next[j];
if (T.ch[j] == T.ch[k]) {
nextval[j] = nextval[k];
}
else {
nextval[j] = next[j];
}
j++;
}
}
通常,模式串的长度m比主串的长度n小很多,且计算next或者nextval函数的时间复杂度为O(m)。因此,对于整个匹配算法来说,所增加的计算next或nextval时值得的。 BF算法的时间复杂度为O(m*n),但是实际接近于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下,才会比BF算法快。KMP算法的最大特点就是主串的指针不需要回溯,整个匹配过程中,主串仅需从头到尾扫描一次,对于处理从外设输入的庞大文件很有效,可以边读边匹配。
头文件:DString.h
#pragma once
#include<windows.h>
typedef struct {//堆串存储结构
char *ch;//若是非空串,则是指向串的起始地址;否则为空
int len;//字符串的长度
}HString;
//串初始化函数
void HStrInit(HString *S) {
S->ch = NULL;
S->len = 0;
}
//串赋值函数
int HStrAssign(HString *S, const char *chars) {
int i = 0;
if (NULL == chars || NULL == S) {
return 0;
}
else {
while (chars[i] != '\0') {
i++;
}
S->len = i;//串S的长度等于串chars的长度
if (0 != S->len) {
if (S->ch != NULL) {
free(S->ch);
}
S->ch = (char *)malloc(sizeof(char)*(S->len + 1));//0号单元不用,故比实际需求多开辟一个空间
if (NULL == S->ch) {//空间开辟失败
return 0;
}
for (i = 1; i <= S->len; i++) {//将chars的内容逐一赋值给S->ch
S->ch[i] = chars[i - 1];
}
}
else {
S->ch = NULL;//当chars的长度为0时,则置S为空串。
}
return 1;
}
}
//打印
void print(HString *S) {
for (int i = 1; i <= S->len; i++) {
printf("%c", S->ch[i]);
}
printf("\n");
}
//BF模式匹配算法
int Index(HString S, int pos, HString T) {
int i = pos;//主串从pos开始
int j = 1;//模式串从头开始
while (i <= S.len&&j <= T.len) {
if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
i++;
j++;
}
else {//当对应字符不相等时
i = i - j + 2;//主串回溯到i-j+2的位置重新比较
j = 1;//模式串从头开始重新比较
}
}
if (j > T.len) {//匹配成功时,返回匹配起始位置
return i - T.len;
}
else {//匹配失败,返回0
return 0;
}
}
//统计BF模式匹配算法的比较次数
int IndexCount(HString S, int pos, HString T) {
int i = pos;//主串从pos开始
int j = 1;//模式串从头开始
int count = 0;
while (i <= S.len&&j <= T.len) {
if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
i++;
j++;
}
else {//当对应字符不相等时
i = i - j + 2;//主串回溯到i-j+2的位置重新比较
j = 1;//模式串从头开始重新比较
}
count++;
}
return count;
}
//KMP模式匹配算法
void Get_Next(HString T, int next[]) {
int j = 1, k = 0;
next[1] = 0;
while (j < T.len) {
if (k == 0 || T.ch[j] == T.ch[k]) {
++j;
++k;
next[j] = k;
}
else {
k = next[k];
}
}
}
void Get_NextVal(HString T, int next[], int nextval[]) {
int j = 2, k = 0;
Get_Next(T, next);
nextval[1] = 0;
while (j <= T.len) {
k = next[j];
if (T.ch[j] == T.ch[k]) {
nextval[j] = nextval[k];
}
else {
nextval[j] = next[j];
}
j++;
}
}
int Index_KMP(HString S, int pos, HString T,int nextval[]) {
int i = pos;//主串从第pos开始
int j = 1;//模式串从头开始
while (i <= S.len&&j <= T.len) {
if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
++i;
++j;
}
else {
j = nextval[j];
}
}
if (j > T.len) {//匹配成功
return i - T.len;//返回匹配的起始位置
}
else {
return 0;
}
}
//统计KMP算法的比较次数
int Index_KMPCount(HString S, int pos, HString T, int nextval[]) {
int i = pos;//主串从第pos开始
int j = 1;//模式串从头开始
int count = 0;
while (i <= S.len&&j <= T.len) {
if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
++i;
++j;
}
else {
j = nextval[j];
}
count++;
}
return count;
}
源文件:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include"DString.h"
int main() {
HString S;
HString T;
HStrInit(&S);
HStrInit(&T);
char a[] = "aaabaaaab";
char b[] = "aaaab";
HStrAssign(&S, a);
HStrAssign(&T, b);
printf("主串:");
print(&S);
printf("模式串:");
print(&T);
printf("BF模式匹配:\n");
int index = Index(S, 1, T);
int count1 = IndexCount(S, 1, T);
printf("index=%d\n", index);
printf("比较次数:%d\n", count1);
printf("KMP模式匹配:\n");
int *next,*nextval;
next = (int *)malloc(sizeof(int)*(T.len + 1));
nextval = (int *)malloc(sizeof(int)*(T.len + 1));
Get_NextVal(T,next,nextval);
printf("next[]数组如下\n");
for (int i = 1; i < (T.len + 1); i++) {
printf("%d ", next[i]);
}
printf("\nnextval[]数组如下:\n");
for (int i = 1; i < (T.len + 1); i++) {
printf("%d ", nextval[i]);
}
printf("\n");
int index1 = Index_KMP(S, 1, T, next);
int count2 = Index_KMPCount(S, 1, T, nextval);
printf("index1=%d\n", index1);
printf("比较次数:%d\n",count2);
system("pause");
return 0;
}