C++数据结构之字符串

这里是C++数据结构的字符串，主要是对字符串的一个总结，以及一些基础操作，还详细讲解了单字符串匹配和多模式匹配算法，详情可以跳转链接进入。

废话说到这里，开始上干货

1.字符串的基础

字符串：简称为串，是由0个或者多个字符组成的有限序列，一般记为$s=a_1{a}_2\dots a_n(0\le n\le \infty )$

1.1 C字符串

在C语言中，我们需要注意的就是，字符串的是以\0结尾，空字符又称为结束符，缩写NULL，数值为0的控制字符，而\0则是转义的意思，目的是告诉编译器，此处不是0，而是空字符。

c中常用的有三种字符结构char, char*, char str[]（char str[n]）。

• char：单独使用，表示单字符，空间为1个字节（如果是字符常量，则有4个字节）
• char*：可以理解为一个指向字符串的指针，指针只有4个字节。
• char str[]：定义一个字符数组，[]没有数值，所以声明的空间取决于你的初始化。
• char str[n]：提前声明字符数组的空间，一般长使用这种方式，不然拼接，复制的时候，可能溢出，需要提前预留一定的空间。

1.2 字符串编码

• ASCII：最早人们制定的127个字符的编码表，学过C的都知道，A的编码是65，a是97。
• GB2312、GBK、GB18030：我国指定的中文编码标准。
• Unicode编码：最常用的如UTF-8编码，UTF-8 编码把一个 Unicode 字符根据不同的数字大小编码成 1 ~ 6 个字节，常用的英文字母被编码成 1 个字节，汉字通常是 3 个字节。

1.3 字符串的存储结构

同样的，字符串的存储结构分为两种，顺序存储和链式存储。

2 字符串操作

字符串的基础操作

• 字符串赋值
• 字符串比较
• 字符串拼接
• 字符串切片

这里做一个简单的总结

这里列举了一些常用操作主要是针对C中的char[]和C++中的string来进行的比较，而_s则是微软提供的接口，需要使用vscode或者vs studio等平台使用才行，可以防止操作溢出的问题。

字符串的匹配问题

字符串匹配（String Matching）：又称模式匹配（Pattern Matching）。可以简单理解为，给定字符串 T 和 p，在主串 T 中寻找子串 p。主串 T 又被称为文本串，子串 p 又被称为模式串（Pattern）。

多模式匹配问题（Multi Pattern Matching）：给定一个文本串 T=t1t2…tn，再给定一组模式串 P=p1,p2,…,pr，其中每个模式串 pi 是定义在有限字母表上的字符串 pi=p1ip2i…pni。要求从文本串 T 中找到模式串集合 P 中所有模式串 pi 的所有出现位置。

具体可以参考一下文章，使用C++解决模式匹配问题

C++之单字符串匹配问题

C++之多模式匹配问题