王道408数据结构——第四章 串（KMP算法）

一、串的定义和实现

字符串简称串，是由零个或多个字符组成的有限序列，一般记为$S='a_1a_2···a_n'$，n称为串的长度。
串中任意多个连续字符组成的子序列称为该串的子串，相应的该串称为主串。某个字符在串中的序号称为字符在串中的位置，子串在串中的位置已子串的第一个字符的位置表示。
两个串相等的充分必要条件是：两个串长度相等，且各个位置对应字符相等

在王道教材中，串的下标从1开始

串的储存表示

1. 定长顺序储存表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元储存串值的字符序列。为每个串，变量分配一个固定长度的储存区，即定长数组。
串的实际长度不能超过MAXSIZE，超过定长的串值会被舍去，称为截断（要客服这种弊端，只能采用动态分配的方法，不限定最大长度）。串的实际长度有两种表达方式：一种是用一个额外的变量存放串的长度；二是在串值后加一个不计入串长的结束标记符号“\0”，此时串长为隐含值。

2. 堆分配储存表示

堆分配储存表示仍然以一组地址连续的存储单元存放串值的字符序列，但他们的存储空间实在程序执行时动态分配的（从一个称为“堆”的自由储存区获取）。

二、模式匹配

求子串（模式串）在主串中的位置。
简单模式匹配算法最坏时间复杂度为O（mn），m和n非别为模式串和主串的长度。
简单模式匹配算法可以改进为KMP算法。

next数组

next[j]的取值为该字符前一个元素的部分匹配值+1，即最长相同前后缀长度+1，同时规定next[1]=0。
例如对于以下模式串，有next数组：

j	1	2	3	4	5	6	7	8	9
模式	a	b	a	a	b	c	a	b	a
next[j]	0	1	1	2	2	3	1	2	3

KMP算法执行

整体上与简单匹配算法类似
当匹配过程产生失配时，指向主串的指针i不变，指向模式串的指针j退回到next[j]的位置并重新进行比较；
当j为0时，i与j同时加1；
若主串的第i个位置和模式串的第一个字符不等，从主串的第i+1个位置开始匹配。
代码如下

int indexKMP(String S, String T, int next[]){  // 主串，模式串，next数组
	int i = 1, j = 1;
	while(i <= S.length && j <= T.length){
		if(j==0 || S.ch[i] == T.ch[j]){  // j等于0或未适配，两指针均向后移动
			i++;
			j++;
		}else{  // 指针失配且j不等于0，i不移动，j移动到next[j]处
			j = next[j];
		}
	if(j > T.length)
		return i - T.length;  // 匹配成功
	else 
		return 0;
}

KMP算法的时间复杂度为$O(m+n)$，而一般情形下普通模式匹配算法实际执行时间近似也为$O(m+n)$，因此至今仍被采用。KMP仅在主串与模式串有很多部分匹配时才显得比普通算法快得多，其主要优点是主串不回溯。

KMP算法优化