C语言数据结构串【BF\KMP算法】

• 感谢UP主：凡三岁爱学习，就我等于苦海之中
• 希望更多的同胞可以看到本篇文章，有空给up主加油呀！
  

串

• 定义：零个或者多个任意字符组成的有限序列

s="xxxxxx";//n>=0
1

• s：串名
• “xxxxx”：串值
• n:串值【n=0 空串】

1 基本概念

• 子串：一个串中任意个连续字符组成的子序列【含空串】称为该串的子串。
• 主串：包含字串的串相应地称为主串
• 字符位置：字符在序列中的序号为该字符在串中的位置
• 字串位置：字串第一个字符在主串中的位置。
• 空格串：有一个或多个空格组成的串【与空串不同】
• 串相等：当且仅当2个串的长度相等，并且各个对应位置上的字符都相同时，这2个字符串才是相等的。
  • 所有的空字符串是相等的。

2 串的类型定义

3 串的字符结构

• 串的顺序存储结构

#define MAXLEN 255
typedef struct {
	char ch[MAXLEN+1];//存储串的一维数组
	int length;//串的当前长度
} SString;
1
2
3
4
5

• 串的链式存储结构–块链结构

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

4 串的模式匹配算法

• 目的：主串中所含字串(模式串)第一次出现的位置（定位）。

4.1 BF[Brute-Force]算法

• 古典的，经典的，朴素的，穷举的算法。
• Index(S,T,pos);
  • 将主串中的第pos个字符和模式串的第一个字符比较。
    • 若相等，继续逐个比较后面的字符。
      • pos的返回位置：i-t.length=3;
    • 若不相等，从主串的下一个字符开始，重新与模式串的第一个字符比较。
      • 回退的公式：i-(j-1)+1=i-j+2
  • 匹配成功,返回S串中匹配成功的第一个字符的序号:否则,返回值为0。
    

4.1.1 案例代码一

//
// Created by HP on 2022/10/28.
//
#include 
#include 
using  namespace std;
#define MAXLENGTH 255
typedef struct {
    char ch[MAXLENGTH + 1];//存储串的一维数组
    int length;//串的当前长度
} SString;

int Index_BF(SString S,SString T,int pos) {
    int i=pos,j=1;//Pos，确定此次匹配开始的位置。
    while (i<=S.length && j<=T.length) {
        if(S.ch[i]==T.ch[j]) {//比较的2个字符相同开始下一次的匹配。
            i++;
            j++;
        }
        else {//主串、子串指针回溯重新开始下一次匹配。
            i=i-j+2;
            j=1;
        }
    }
    if(j>=T.length) {
        return i-T.length;//匹配成功返回匹配的第一个字符的下标。
    }
    else return 0;//模式匹配不成功。
}

int main() {
    SString s1;
    int len,option;
    cout<<"请输入主串的字符个数：";
    cin>>len;
    s1.length=len;
    cout<<"请输入主串的内容：";
    for(int i=1;i<=len;i++) {
        cin>>s1.ch[i];
    }
    SString s2;
    cout<<"请输入模式串的字符个数：";
    cin>>len;
    s2.length=len;
    cout<<"请输入模式串的内容：";
    for(int i=1;i<=len;i++) {
        cin>>s2.ch[i];
    }
    cout<<"请输入开始匹配的位序：";
    cin>>option;
    int res=Index_BF(s1,s2,option);
    cout<<res<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

4.1.2 案例代码二

• 学习视频地址

//
// Created by HP on 2022/10/28.
//
#include 
#include 
using  namespace std;

typedef struct String{
    char* data;
    int len;
}String;
String* InitString() {
    String *S=(String*)malloc(sizeof(String));
    S->data=NULL;
    S->len=0;
};
void stringAssign(String* s,char* data) {
    //如果s的指向不为空，就将s释放，方便下面对其进行赋值
    if(s->data) {
        free(s->data);
    }
    //统计data字符串的长度，但要注意不要改变data的指向，所以定义了一个临时指针
    int len=0;
    char* temp=data;
    while(*temp) {
        len++;
        temp++;
    }
    //如果输入的时只有一个空格的空格串，就做相应的处理
    //否则，利用temp指针将字符串赋值给s->data
    if(len==0) {
        s->data=NULL;
        s->len=0;
    }
    else {
        temp=data;
        s->len=len;
        //开辟的长度要加1，因为要保存最后的‘\0’字符
        s->data=(char*)malloc(sizeof(char) *(len+1));
        for(int i=0;i<len;i++,temp++) {
            s->data[i]=*temp;
        }
    }
}

void printString(String* s) {
    for(int i=0;i<s->len;i++) {
        printf(i==0 ? "%c":"-> %c",s->data[i]);
    }
    cout<<endl;
}

void forceMatch(String *master,String *sub) {
    int i=0,j=0;
    while(i<master->len && j<sub->len) {
        if(master->data[i]==sub->data[j]) {
            i++;
            j++;
        }
        else {
            i=i-j+2;
            j=0;
        }
    }
    if(j==sub->len) {
        cout<<"success"<<endl;
    }else {
        cout<<"fail"<<endl;
    }
}

int main() {
    //对字符串进行初始化
    String *s1=InitString();
    String *s2=InitString();
    int len;
    cout<<"请输入主串的字符个数：";
    cin>>len;
    cout<<"请输入主串的内容：";
    char arr[len+1];
    arr[len]='\0';
    for(int i=0;i<len;i++) {
        cin>>arr[i];
    }
    cout<<"请输入模式串的字符个数：";
    cin>>len;
    cout<<"请输入模式串的内容：";
    char arr2[len+1];
    arr2[len]='\0';
    for(int i=0;i<len;i++) {
        cin>>arr2[i];
    }
    stringAssign(s1,arr);
    stringAssign(s2,arr2);
    printString(s1);
    printString(s2);
    forceMatch(s1,s2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

4.2 KMP算法

• 推荐的学习视频【简单、易懂】
  
  求解next数组前要懂得以下几个概念

1. next数组定义：当主串与模式串的某一位字符不匹配时，模式串要回退的位置其值
2. next[j]：第位字符前面j-1位字符组成的子串的前后重合字符数+1

4.2.-1 手算Next数组

• 本文的手算方法，就是仅仅是看j前的字符串最长公共前后缀个数+1
  
  
  

4.2.0 图解

• up主总结：
  • 看门牌算法
    

4.2.1 案例代码一

//
// Created by HP on 2022/10/29.
//
#include 
using namespace std;
#define MAXSTRLEN 255//用户在255以内定义最大的串长
typedef unsigned char SString[MAXSTRLEN+1];//0号位置存放串的长度
void GetNext(int next[],SString S) {
    //求模式串的next数组函数值并存入数组next
    int i=1,j=0;
    next[i]=j;//默认next[1]=0;
    while(i<=S[0]) {
        if(j==0 || S[i]==S[j]) {
            next[++i]=++j;
        }else {
            j=next[j];
        }
    }
}

int IndexKmp(SString S,SString T,int pos,int next[]) {
    int i=pos,j=1;
    while(i<=S[0] && j<=T[0]) {
        if(j==0 || S[i]==T[j]) {
            i++;j++;
        }else {
            j= next[j];
        }
    }
    if(j>T[0]) {
        return i-T[0];
    }else {
        return -1;
    }
}
int main() {
    SString s1,s2;
    int nums,pos;
    cout<<"请输入字符的总个数：";
    cin>>nums;
    s1[0]=nums;
    cout<<"请输入主字符串：";
    for(int i=1;i<=nums;i++) {
        cin>>s1[i];
    }
    cout<<"请输入字符的总个数：";
    cin>>nums;
    s2[0]=nums;
    cout<<"请输入模式符串：";
    for(int i=1;i<=nums;i++) {
        cin>>s2[i];
    }
    int next[s2[0]+1];//多开辟一个，因为next的下标是从1开始存储的
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%c":"-> %c",s2[i]);
    }
    GetNext(next,s2);
    cout<<endl;
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%d":"-> %d",next[i]);
    }
    cout<<endl;
    cout<<"请输入开始匹配的序号:";
    cin>>pos;
    cout<<"匹配主串的首字母序号："<<IndexKmp(s1,s2,pos,next);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

4.2.2 案例代码二

• 学习视频的地址

//
// Created by HP on 2022/10/28.
//
#include 
using namespace  std;
#include 

typedef struct String {
    char* data;
    int len;
} String;
String* InitString() {
    String* s=(String*)malloc(sizeof(String));
    s->data=NULL;
    s->len=0;
    return s;
}

void stringAssign(String* s,char* data) {
    //如果s的指向不为空，就将s释放，方便下面对其进行赋值
    if(s->data) {
        free(s->data);
    }
    //统计data字符串的长度，但要注意不要改变data的指向，所以定义了一个临时指针
    int len=0;
    char* temp=data;
    while(*temp) {
        len++;
        temp++;
    }
    //如果输入的时只有一个空格的空格串，就做相应的处理
    //否则，利用temp指针将字符串赋值给s->data
    if(len==0) {
        s->data=NULL;
        s->len=0;
    }
    else {
        temp=data;
        s->len=len;
        //开辟的长度要加1，因为要保存最后的‘\0’字符
        s->data=(char*)malloc(sizeof(char) *(len+1));
        for(int i=0;i<len;i++,temp++) {
            s->data[i]=*temp;
        }
    }
}

void printString(String* s) {
    for(int i=0;i<s->len;i++) {
        printf(i==0 ? "%c":"-> %c",s->data[i]);
    }
    cout<<endl;
}

int* getNext(String* s) {
    int* next=(int*)malloc(sizeof(int)*s->len);
    int i=0,j=-1;
    next[i]=j;
    while(i<s->len-1) {
        if(j==-1 || s->data[i]==s->data[j]) {
            i++;
            j++;
            next[i]=j;
        }else {
            j=next[j];
        }
    }
    return next;
}
void printNext(int* next,int len) {
    for(int i=0;i<len;i++) {
        printf(i==0 ? "%d":"-> %d",next[i]+1);
    }
    cout<<endl;
}

void KmpMatch(String* master,String* sub,int* next) {
    int i=0,j=0;
    while( i<master->len && j<sub->len) {
        if(j==-1 || master->data[i]==sub->data[j]) {
            i++;
            j++;
        }else {
            j= next[j];
        }
    }
    if(j==sub->len) {
        cout<<"match success!"<<endl;
    }else {
        cout<<"match fail!"<<endl;
    }
}

int main() {
    //对字符串进行初始化
    String *s1=InitString();
    String *s2=InitString();
    int len;
    cout<<"请输入主串的字符个数：";
    cin>>len;
    cout<<"请输入主串的内容：";
    char arr[len+1];
    arr[len]='\0';
    for(int i=0;i<len;i++) {
        cin>>arr[i];
    }
    cout<<"请输入模式串的字符个数：";
    cin>>len;
    cout<<"请输入模式串的内容：";
    char arr2[len+1];
    arr2[len]='\0';
    for(int i=0;i<len;i++) {
        cin>>arr2[i];
    }
    stringAssign(s1,arr);
    stringAssign(s2,arr2);
    printString(s1);
    printString(s2);
    int *next= getNext(s2);
    printNext(next,len);
    KmpMatch(s1,s2,next);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

4.3 KMP算法优化

4.3.1 问题·引子

//
// Created by HP on 2022/10/29.
//
#include 
using namespace std;
#define MAXSTRLEN 255//用户在255以内定义最大的串长
typedef unsigned char SString[MAXSTRLEN+1];//0号位置存放串的长度
// void GetLength(SString &S) {
//     int length=0;
//     unsigned char *temp=&S[1];
//     while(*temp) {
//         temp++;
//         length++;
//     }
//     S[0]=length;
// }
void GetNext(int next[],SString S) {
    //求模式串的next数组函数值并存入数组next
    int i=1,j=0;
    next[i]=j;//默认next[1]=0;
    while(i<=S[0]) {
        if(j==0 || S[i]==S[j]) {
            next[++i]=++j;
        }else {
            j=next[j];
        }
    }
}

void GetNextVal(int nextVal[],SString S) {
    //求模式串的next数组函数值并存入数组next
    int i=1,j=0;
    nextVal[i]=j;//默认next[1]=0;
    while(i<=S[0]) {
        if(j==0 || S[i]==S[j]) {
            ++i;
            ++j;
            if(S[i]!=S[j]) {
                nextVal[i]=j;
            }else {
                nextVal[i]=nextVal[j];
            }
        }else {
            j=nextVal[j];
        }
    }
}

int IndexKmp(SString S,SString T,int pos,int next[]) {
    int i=pos,j=1;
    while(i<=S[0] && j<=T[0]) {
        if(j==0 || S[i]==T[j]) {
            i++;j++;
        }else {
            j= next[j];
        }
    }
    if(j>T[0]) {
        return i-T[0];
    }else {
        return -1;
    }
}
int main() {
    SString s1,s2;
    int nums,pos;
    cout<<"请输入字符的总个数：";
    cin>>nums;
    s1[0]=nums;
    cout<<"请输入主字符串：";
    for(int i=1;i<=nums;i++) {
        cin>>s1[i];
    }
    //GetLength(s1);
    cout<<"请输入字符的总个数：";
    cin>>nums;
    s2[0]=nums;
    cout<<"请输入模式符串：";
    for(int i=1;i<=nums;i++) {
        cin>>s2[i];
    }
    //GetLength(s2);
    int next[s2[0]+1];//多开辟一个，因为next的下标是从1开始存储的
    //next[0]=s2[0];//记录长度
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%c":"-> %c",s2[i]);
    }
    cout<<endl;
    GetNext(next,s2);
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%d":"-> %d",next[i]);
    }
    cout<<endl;
    cout<<"请输入开始匹配的序号:";
    cin>>pos;
    cout<<"匹配主串的首字母序号："<<IndexKmp(s1,s2,pos,next)<<endl;

    cout<<"======================"<<endl;

    GetNextVal(next,s2);
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%c":"-> %c",s2[i]);
    }
    cout<<endl;
    for(int i=1;i<=s2[0];i++) {
        printf(i==1 ? "%d":"-> %d",next[i]);
    }
    cout<<endl;
    cout<<"请输入开始匹配的序号:";
    cin>>pos;
    cout<<"匹配主串的首字母序号："<<IndexKmp(s1,s2,pos,next);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113