字符串匹配

Question

一、字符串定义

串（String）是由零个或多个字符组成的有限序列，又名叫字符串。串可以是空串。

二、 字符串的比较

字符串比较大小跟传统的数字比较有点差别，很容易我们知道 2 比 1 要大，可要是 "FishC" 和 "fish.com" 呢？要怎么比较？

其实，比的就是字符串里每个字符的 ASCII 码大小，因为 'F'==70、'f'==102，所以 'f'>'F'，"fishc.com" > "FishC"。

其实这样的比较大小没有多大意义，字符串的比较我们更重视是否相等！

三、字符串的存储结构

字符串的存储结构与线性表相同，也分为顺序存储结构和链式存储结构。

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

按照预定义的大小，为每个定义的字符串变量分配一个固定的存储区，一般用定长数组来定义。

与线性表相似，既然是固定长度的存储区，就存在一个空间分配不灵活的问题，那么会考虑用链式存储结构。

不同的是字符串我们一般都是连在一起表述的，“断章取义”的情况并不多，所以习惯上我们通常会直接定义一个足够长度的存储区来存储的。

四、BF（Brute Force）算法

BF 算法属于朴素的模式匹配算法，他的核心思想是：

有两个字符串 S 和 T，长度为 N 和 M。首先 s[1] 和 T[1] 比较，若相等，则再比较 s[2] 和 T[2]，一致到 T[M] 为止；若 s[1] 和 T[1] 不等，则 T 向右移动一个字符的位置，再依次进行比较。

该算法最坏的情况下要运行 M(N-M+1)次比较，时间复杂度为 O(MN)。

在这里 S 是主串，T 是字串，这种字串的定位操作通常称作串的模式匹配。

五、KMP 算法

KMP 算法的核心就是避免不必要的回溯，那么什么是不必要的呢？问题由模式串决定，而不是由目标串决定