前言
由于计算机的发展，人们发现对于非数值类型的处理越来越多，进而衍生出来串。
串也就是我们所使用的字符串。
如下所有代码需要做如下引用：
1
2
3
4
5
6
| #include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define _CRT_SECURE_NO_WARNINGS
|
关于上述引用的说明，原因参考关于C语言的一些零碎思考
串的定义和基本操作
串的定义
串，即字符串（String）是由零个或者多个字符组成的有限序列，一般记作S='a1,a2,...an'（$n \geqslant 0 $）。
其中S是串的名称，单引号括起来的字符序列是串的值，其中串字符的个数称为串的长度。当 $n =0$ 的时候称为空串。代码示例：
子串：串中任意连续个字符组成的子序列，例如：上面的子串Hello。
串的数据对象限定为：字符集（如中文字符，英文字符）。
串的基本操作
| 函数 |
说明 |
StrAssign() |
赋值操作，给字符串赋值 |
StrCopy() |
复制操作，将两个字符串进行复制 |
StrEmpty() |
判断字符串是否为空 |
StrLength() |
获取字符串长度，返回串元素的个数 |
ClearString() |
清空操作，清空串为空串 |
DestoryString() |
销毁串 |
Concat() |
串链接，链接两个字符串返回新串 |
SubString() |
获取子串，根据元素位置和长度返回其子串 |
Index() |
定位子串的位置（第一次出现的） |
StrCompare() |
串比较操作 |
串的物理结构
串的存储结构
顺序存储
静态顺序存储
1
2
3
4
5
| #define MaxLen 255
typedef struct {
char ch[MaxLen];
int length;
}SString;
|
动态顺序存储
1
2
3
4
| typedef struct {
char *ch;
int length;
}DString;
|
链式存储
1
2
3
4
| typedef struct stringNode {
char ch;
struct stringNode* next;
}StrNode;
|
由于char类型只占一个字节，而struct stringNode*类型指针占四个字节，所以采用上述链式存储的存储密度很低。如果想要使用链式存储，可以尝试使用如下改进：
1
2
3
4
| typedef struct stringNode {
char ch[4];
struct stringNode* next;
}StrNode;
|
这样每个节点存储四个字节的字符和四个字节的指针。
基本操作的实现
注：本示例基本操作的实现是基于静态顺序的存储结构
截取（获取）子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
bool SubString(SString* s, SString* sub, int pos, int len) {
if (pos + len > s->length) {
printf("子串索引超出主串\n");
return false;
}
printf("截取的字符串为：");
for (int i = 0; i < len; i++)
{
sub->ch[i] = s->ch[pos + i];
printf("%c", sub->ch[i]);
}
printf("\n");
sub->length = len;
return true;
}
|
比较字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int StrCompare(SString* s1, SString* s2) {
if (s1->length==0 || s2->length==0)
{
printf("存在空串");
return -99;
}
printf("要匹配的字符串为：");
for (int j = 0; j < s2->length; j++)
{
printf("%c",s2->ch[j]);
}
printf("\n");
for (int i = 0; i < s1->length &&i<s2->length; i++)
{
if (s1->ch[i]!=s2->ch[i])
{
return s1->ch[i] - s2->ch[i];
}
}
return s1->length - s2->length;
}
|
定位子串的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int Index(SString* s, SString* sub) {
if (s->length == 0 || sub->length == 0)
{
printf("存在空串");
return -99;
}
SString temp;
for (int i = 0; i < s->length; i++)
{
SubString(s, &temp, i, sub->length);
if (StrCompare(&temp, sub) == 0) {
printf("子串匹配成功，位置为：%d", i+1);
return i+1;
}
}
printf("未匹配到字符串");
return 0;
}
|
测试代码
1
2
3
4
5
| int main() {
SString s = { { 'h','e', 'l', 'l', 'o' },5 };
SString sub = { { 'l', 'o' },2 };
Index(&s, &sub);
}
|
运行结果：
朴素模式匹配算法
通俗来说就是上面所实现的字符串的操作的“定位子串的位置”，俗称“暴力解”。
现在来通过数组下标来实现朴素模式匹配算法，也就是上面的定位操作，代码示例：
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
|
int NaiveMatch(char* s[],char* m[]) {
int i = 0;
char temp[MaxLen];
for (int j = 0; j < (strlen(s)-strlen(m)+1); j++)
{
SubString(s, temp, i, strlen(m));
if (StrCompare(temp, s)==0)
{
i++;
}
else
{
i = 0;
j = j - i + 2;
}
if (i>strlen(m))
{
printf("已匹配到字符串，位置:%d", strlen(s) - strlen(m)+1);
return strlen(s) - strlen(m)+1;
}
}
printf("匹配失败");
return -1;
}
int main() {
char s[MaxLen] = { 'h','e', 'l', 'l', 'o' };
char sub[MaxLen] = { 'l', 'o' };
NaiveMatch(&s, &sub);
}
|
运行结果：
KMP算法
KMP算法简介
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
如上来源：百度百科kmp算法
KMP算法是在上面的朴素模式匹配算法的基础上改进而来
KMP算法实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
bool GetNext(char* m[],char* next[]) {
int i, k;
i = 1;
k = 0;
next[1] = 0;
while (i<strlen(m))
{
if (k==0 || m[i]==m[k])
{
++i;
++k;
next[i] = k;
}
else
{
k = next[k];
}
}
}
|
改进KMP算法
不想写，欠……
这部分内容有点繁杂，我在尝试使用更加直观的方法来说明。如上也同理，仅贴代码示例；
End
救命越来越不想写了，属实太难用文字解释了，如果用视频的话要比文字快很多。
