[TOC]
说明：以下文字来源《大话数据结构》 作者：程杰。
定义
串是由零个或者多个字符组成的有限序列，又名字符串。
串的存储结构
串的存储结构与线性表相同，分为两种。
串的顺序存储结构
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。安装预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义。
串的链式存储结构
对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用"#“或者其他非串字符补全。
对比
串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。
KMP模式匹配算法
转载：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
字符串匹配是计算机的基本任务之一。
举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串"ABCDABD"？
许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。
「真诚赞赏，手留余香」
真诚赞赏，手留余香
使用微信扫描二维码完成支付
