前言

由于计算机的发展，人们发现对于非数值类型的处理越来越多，进而衍生出来串。

串也就是我们所使用的字符串。

如下所有代码需要做如下引用：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

//如果你使用的是Visual Studio，则还需要添加如下一条引用
#define _CRT_SECURE_NO_WARNINGS

关于上述引用的说明，原因参考关于C语言的一些零碎思考

串的定义和基本操作

串的定义

串，即字符串（String）是由零个或者多个字符组成的有限序列，一般记作S='a1,a2,...an'（$n \geqslant 0 $）。

其中S是串的名称，单引号括起来的字符序列是串的值，其中串字符的个数称为串的长度。当 $n =0$ 的时候称为空串。代码示例：

S = "Hello,World"

子串：串中任意连续个字符组成的子序列，例如：上面的子串Hello。

串的数据对象限定为：字符集（如中文字符，英文字符）。

串的基本操作

函数	说明
`StrAssign()`	赋值操作，给字符串赋值
`StrCopy()`	复制操作，将两个字符串进行复制
`StrEmpty()`	判断字符串是否为空
`StrLength()`	获取字符串长度，返回串元素的个数
`ClearString()`	清空操作，清空串为空串
`DestoryString()`	销毁串
`Concat()`	串链接，链接两个字符串返回新串
`SubString()`	获取子串，根据元素位置和长度返回其子串
`Index()`	定位子串的位置（第一次出现的）
`StrCompare()`	串比较操作

串的物理结构

串的存储结构

顺序存储

静态顺序存储

#define MaxLen 255	//定义串的最大长度为255
typedef struct {
	char ch[MaxLen];
	int length;	//串的长度
}SString;

动态顺序存储

typedef struct {
	char *ch;	//用malloc函数申请一片空间，指针指向头地址
	int length;	//串的长度
}DString;

链式存储

typedef struct stringNode {
	char ch;	//每个节点存储一个字符
	struct stringNode* next;
}StrNode;

由于char类型只占一个字节，而struct stringNode*类型指针占四个字节，所以采用上述链式存储的存储密度很低。如果想要使用链式存储，可以尝试使用如下改进：

typedef struct stringNode {
	char ch[4];	//每个节点存储一个字符
	struct stringNode* next;
}StrNode;

这样每个节点存储四个字节的字符和四个字节的指针。

基本操作的实现

注：本示例基本操作的实现是基于静态顺序的存储结构

截取（获取）子串

//求子串（获取子串）
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;
}

比较字符串

//比较操作
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;
}

定位子串的位置

//定位操作
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;
}

测试代码

int main() {
	SString s = { { 'h','e', 'l', 'l', 'o' },5 };
	SString sub = { { 'l', 'o' },2 };
	Index(&s, &sub);
}

运行结果：

朴素模式匹配算法

通俗来说就是上面所实现的字符串的操作的“定位子串的位置”，俗称“暴力解”。

现在来通过数组下标来实现朴素模式匹配算法，也就是上面的定位操作，代码示例：

//朴素模式匹配算法——利用数组下标
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++;	//模式串指针+1
		}
		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算法实例

//求Next数组
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];
		}
	}
}