串的总结——基本知识要点汇总

【PS：知识点会不定期进行编辑更新和完善，了解最近更新内容可参看更新日志，欢迎留言】

更新日志

最近更新：

• 暂时没有编辑记录，后续会持续完善优化

串的相关概念

• 定义：线性存储的一组数据（默认是字符）
• 特殊操作集
  • 求串的长度
  • 比较两串是否相等
  • 两串相接
  • 求子串
  • 插入子串
  • 匹配子串
  • 删除子串
    ……
• C语言中常用的串运算
  调用标准函数库#include<string.h>
  • 串比较，strcmp(char s1,char s2)
  • 串复制，strcpy(char s1,char s2)
  • 串连接，strcat(char s1,char s2)
  • 求串长，strlen(char s)
    ……

串的存储

串的顺序存储

串的链式存储

串的模式匹配

C语言库函数strstr

• 函数原型：char* strstr(char* string,char* pattern)
• 函数参数：string为要被检索的字符串，pattern为要进行匹配的模式字符串
• 函数返回值：函数返回在字符串string中第一次出现字符串pattern的位置，如果未匹配成功则返回NULL

举例：在字符串"This is a simple example.“中匹配字符串"simple”

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

#define NotFound NULL
typedef char* Position;

int main()
{
	char string[] = "This is a simple example.";
	char pattern[] = "simple";
	Position p = strstr(string, pattern);
	if (p == NotFound) { printf("Not Found.\n"); }
	else { printf("%s\n", p); }
	return 0;
}

测试结果如下

BF算法

算法思想：朴素的穷举匹配，即将要进行检索的目标串string的第一个字符与要进行匹配的模式串的第一个字符进行匹配，若相等则继续比较string的第二个字符与pattern的第二个字符；若不相等，则将string下一个字符与pattern当前字符进行比较，依次一直进行下去，直到匹配出结果或匹配结束。
【算法代码后续更新】

KMP算法

next值与nextval值的求解

【暂时只总结求解方法，具体解释和原理后续更新】

• 核心思想：寻找当前字符之前的字符串中头部和尾部相等的长度最大的子串
• 举例：默认字符元素从下标为1的数组单元开始存

数组下标为1和2的数组单元next值是一定的，分别为0和1

接下来数组单元的next值的求解，需要寻找这个字符之前的字符串中头部和尾部相等的长度最大的子串，这个子串的长度+1即为此字符的next值，如果这个字符之前的字符串头部和尾部没有可以匹配的子串，则此字符的next值为1

例如此时数组下标为3字符b之前的字符串"aa"，头部和尾部相同的长度最大的子串为“a”，长度为1，因此它的next值为1+1=2

数组下标为4的字符a之前的字符串"aab"，头部和尾部没有可以匹配的子串，因此它的next值为1

数组下标为5的字符a之前的字符串"aaba"，头部和尾部可以匹配的最大长度子串为“a”，因此它的next值为1+1=2

数组下标为6的字符c之前的字符串"aabaa"，头部和尾部可以匹配的最大长度子串为“aa”，因此它的next值为1+2=3

【此处需注意，寻找字符串头部和尾部可以匹配的最大长度子串时，顺序需保持一致，如字符串"aabaa"头部和尾部长度为3的子串分别为"aab"与"baa"，二者匹配不成功】

nextval值需要根据next值求解，数组下标为1的字符nextval值是一定的，为0。

接下来数组单元的next值的求解，以它的next值为下标去访问数组单元，比较两个单元的字符是否相等，若相等则它们的nextval值也保持一致，若不相等，则此字符的nextval值与next值保持一致

例如此时数组下标为2字符a的next值为1，将其作为数组下标对应的字符为a，两者相等，则nextval值也保持一致

数组下标为3字符b的next值为2，将其作为数组下标对应的字符为a，两者不相等，则它的nextval值与next值保持一致

依此继续进行求解，可完成全部求解

【后续持续更新……】