目录

1. 串的定义

2. 串的比较

3. 串的抽象数据类型

4. 串的存储结构

4.1 串的顺序存储结构

4.2 串的链式存储结构

5. 朴素的模式匹配算法

6. KMP模式匹配算法

1. KMP模式匹配算法原理

2. next数组值推荐

3. KMP模式匹配算法实现

4. KMP模式匹配算法改进

5. nextval数组值推导

7. 总结

串：串（string）是由零个或多个字符组成的有限序列，又叫字符串。

在介绍串的基本知识点之前，先举个小例子，是关于诗句中的回文诗。

我们古人没有电影电视，没有游戏网络，所以文人们就会想出一些文字游戏来娱乐。比如宋代的李禺写了这样一首诗：“枯眼望遥山隔水，往来曾见几心知？壶空怕酌一杯酒，笔下难成和韵诗。途路阻人离别久，讯音无雁寄回迟。孤灯夜守长寥寂，夫忆妻兮父忆儿。”显然这是老公想念老婆和儿子的诗句。曾经和妻儿在一起，尽享天伦之乐，现在一个人长久没有回家，也不见书信返回，望着油灯想念亲人，能不伤感吗？

可再仔细一读发现，这首诗竟然可以倒过来读：“儿忆父兮妻忆夫，寂寥长守夜灯孤。迟回寄雁无音讯，久别离人阻路途。诗韵和成难下笔，酒杯一酌怕空壶。知心几见曾来往，水隔山遥望眼枯。”这表达了什么意思呢？哈哈，表达了妻子对丈夫的思念。老公离开好久，路途遥远，难以相见。写信不知道写什么，独自喝酒也没什么兴致。只能和儿子夜夜守在家里一盏孤灯下，苦等老公的归来。

这种诗体叫做回文诗。它是一种可以倒读或反复回旋阅读的诗体。刚才这首就是正读是丈夫思念妻子，倒读是妻子思念丈夫的古诗。是不是感觉很奇妙呢？

在英语单词中，同样有神奇的地方。“即使是lover也有个over,即使是friend也有个end,即使是believe也有个lie。”你会发现，本来不相干，甚至对立的两个词，却有某种神奇的联系。这可能是创造这几个单词的那些智者们也没有想到的问题。

接下来谈谈这些单词或句子组成字符串的相关问题。

早先的计算机在被发明时，主要作用是做一些科学和工程的计算工作，也就是现在我们理解的计算器，只不过它比小小计算器功能更强大、速度更快一些。后来发现，在计算机上作非数值处理的工作越来越多，使得我们不得不需要引入对字符的处理。于是就有了字符串的概念。

生活中有哪些比较常见关于串的应用呢？比如我们现在常用的搜索引擎，当我们在文本框中输入“数据”时，它已经把我们想要的“数据结构”列在下面了。显然这里网站作了一个字符串查找匹配的工作：

我们先看看串的定义：

串：串（string）是由零个或多个字符组成的有限序列，又叫字符串。

一般记为s=“aia2……an”（n>0)，其中，s是串的名称，用双引号括起来的字符序列是串的值，注意双引号不属于串的内容。(1< i T，返回值 > 0，若S = T，返回0，若S < T，返回值 < 0。 Concat(T, S1, S2)：用T返回由S1和S2联接而成的新串。 SubString(Sub, S, pos, len)：串S存在，1≤pos≤StrLength(S), 且0≤len≤StrLength(S) - pos + 1， 用Sub返回串S的第pos个字符，用Sub返回串S的第pos个字符起长度为len的字串。 Index(S, T, pos)：串S和T存在，T是非空串，1≤pos≤StrLength(S)。 若主串S中存在和串T相同的子串，则返回它在主串S中第pos个字符之后第一个出现的位置，则返回0。 Replace(S, T, V)：串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。 StrInsert(S, pos, T)：串S和T存在，1≤pos≤StrLength(S) + 1。在串S的第pos个字符之前插入串T。 StrDelete(S, pos, len)：串S存在，1≤pos≤StrLength(S) - len + 1。从串S中删除第pos个字符起长度为len的子串。 endADT

先看看一个操作 Index 的实现算法：