串---BF算法和KMP算法

提示：以下是本篇文章正文内容

一、串的定义

串(string)是由零个或多个字符组成的有限序列

子串：串中任意个连续的字符组成的子序列

主串：包含子串的串

空串：0个字符的串

子串的位置：子串的第一个字符在主串中的序号

S = "abcd123"
T1 = "abcd"
T2 = "abcd124"
T1是S的子串，T2不是S的子串，T1位置在S中为0

字符串的前缀是指字符串的任意首部 字符串的后缀是字符串的任意尾部

比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”，后缀有“c”,“bc”,“bbc”,“abbc”

二、串的存储 1.顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的

2.链式存储结构

对应串的链式存储结构，与线性表是相似的，但是由于串的结构的特殊性，结构中的每个元素数据是一个字符，就会存在很大的浪费空间。

因此，一个结点可以存储多个字符，若最后一个结点没有被占满，可以用"#"或者其他非串值字符代替补全