字符串

定义

1. 字符串是由零个或多个字符组成的有限序列。
2. 字符串有很多特殊的操作，如strcpy, concat, substring等。

表示

定长顺序存储表示

字符串的结束

在C语言中，也可以使用\0来表示字符串的结束，但无法直接得到字符串的长度，在一些操作中可能有所不便。

堆分配存储表示

块链存储表示

模式匹配算法

定位函数

以下算法基于顺序存储的字符串结构，且利用第一个存储单元存放字符串的长度。

整体思路：

1. 将指针指向主串的第pos位和子串的第一位，准备匹配。
2. 逐个移动指针，如果指向的内容相同，则继续向后移动。
3. 如果指向的内容不同，指向子串的指针回到第一位，指向主串的指针回退j-2位（与原本第一次成功开始匹配的位置差j-1位，而该位已不可能匹配成功，因此向后移动到j-2位）
4. 匹配结束后，若指向子串的指针仍然指向子串，意味着还有内容未被匹配到，即匹配失败；否则当前位置向前移动t的长度，即为子串开始的位置。

KMP

KMP可以在$O(n+m)$的时间完成模式匹配操作。当出现失配时，KMP算法将模式串$p$（子串）移动一段尽可能远的距离再进行比较。

设主串$s = '{s_1s_2s_3...s_n}'$， 模式串 $p = '{p_1p_2p_3...p_m}'$。要考虑的问题是：当匹配过程中产生失配（$s_i != p_j$)，接下来应该选择主串的哪个字符和模式串的哪个字符开始比较。

假设应该从模式串的第$k(k < j)$ 个字符继续比较，那么存在一个最大的$k$ ，满足：

$$'{p_1p_2...p_{k-1}}' = '{s_{i-k+1}s_{i-k+2}...s_{i-1}}'$$

已经得到的部分匹配可以得出：

$$'{p_{j-k+1}p_{j-k+2}...p_{j-1}}' = '{s_{i-k+1}s_{i-k+2}...s_{i-1}}'$$

根据两式可以得出：

$$'{p_1p_2...p_{k-1}}' = '{p_{j-k+1}p_{j-k+2}...p_{j-1}}'$$

反之，若模式串中存在满足上面结论的两个子串，则在匹配中，若主串第$i$个和模式串第$j$个出现不同，只需要移动模式串，使模式串第$k$个和主串第$i$个进行比较：模式串的前$k-1$个已被确认和主串对应位置匹配，无需再次比较。

为了得到不同的$j$下符合$'{p_1p_2...p_{k-1}}' = '{p_{j-k+1}p_{j-k+2}...p_{j-1}}'$的$k$， 还需要next数组。 该数组记录了每个$j$对应的$k$的值。

以下是next函数的定义：

$$next[j] = \begin{cases} 0, j=1 \\ Max\{k | 1<k<j, '{p_1p_2...p_{k-1}}' = '{p_{j-k+1}p_{j-k+2}...p_{j-1}}'\},集合非空时\\ 1,others \\ \end{cases}$$

实现：

next函数的实现:

由定义可知：设$next[j]=k$，

$$next[1]=0$$

$$'{p_1p_2...p_{k-1}}' = '{p_{j-k+1}p_{j-k+2}...p_{j-1}}' (1<k<j)$$

特殊情况下，$p_k=p_j$，此时根据定义可以得出：

$$'{p_1p_2...p_{k}}' = '{p_{j-k+1}p_{j-k+2}...p_{j}}' (1<k<j)$$

根据$next[j]=k$可得：

$$next[j+1] = k + 1 = next[j] + 1$$

若$p_k \neq p_j$，可以将求next函数值看作以模式串自身为主串和模式串的模式匹配问题。

在将模式串与自身模式匹配的过程中，由于$p_k \neq p_j$，即$p_k$和$p_j$比较时出现失配，因此应将模式串滑动到用模式串的第$next[k]$个字符和主串中的第$j$个字符作比较。

假设$next[k]=k'$，且$p_j=p_{k'}$，说明主串的第$j+1$个字符前存在一个长度为$k'$的最长子串，即：

$$'{p_1...p_{k'}}'='{p_{j-k'+1}...p_j}'$$

由此式得出：

$$next[j+1] = k' + 1 = next[k] + 1$$

当$p_j \neq p_{k'}$， 则继续移动模式串，直到第$next[k']$个字符和$p_j$相等，直至匹配成功或结束：

$$next[j+1] = 1$$