数学和计算机科学板块_辛酸网

数据结构与算法6

串

  串，数据结构中概念上的字符串，一种元素内容受限的线性表，里面的元素都是字符。串和现实中真正的字符串有所类似，但是本质上有区别——现实中的字符串，结尾有空字符'\0'表示字符串内容结束了，但是串没有。另外，现实中的字符串从0开始，最前面的字符必然是第0个字符，但是串不是。串中规定最前面的是第1个元素。比较离谱的是，一般来说我们可以对线性表中的某个元素做什么事情，但是串却在概念上不允许我们对其中某一个字符做什么，只能截取某一个片段对其做什么事情。也就是说，一般的线性表里最基本的操作对象是数据元素，而串中不是，串中被操作的内容还是一个串。只不过这样的串是前面那个串的一部分，所以叫做子串，而包含了子串的串被称为主串。

  串可以直接顺序存储，那就是一个单纯的字符串而已，虽然串的概念中没有空字符，但是存储器中不可能没有。串也可以链式存储，这时就能避免多出来的空字符，不过因为有指针域所以还会多占用更多的空间。对于一个主串内的多个子串还可以进行索引存储。首先我们顺序存储主串mainstring。为了确定一个子串，我们需要知道它在哪里以及多长。现在定义子串类型：

typedef struct
{
	char name[length_of_name];
	int start;//开始处下标，当然用char指针也行
	int end;//结尾处下标
	char *startaddress;//首尾处指针
	char *endaddress;
	int length;//长度
}substring;

  具体怎么定义要看实际情况，但总体而言就是要确保能唯一确定这个子串。开始处的位置是一定要存储的。（除非你想从后往前来那就魔幻啦。）如果子串类型里定义了长度，那么根据主串的内容，我们遍历一定长度后就能确定子串，毕竟开始处下标加上长度就是结尾处下标，指针的话就乘以单个字符的大小罢了。所以主串空间里不需要再插入空字符，定义了结尾位置亦然。但要是这两个都没有在子串中定义，我们能不能成功确定子串呢？可以，但要在主串中插入若干空字符。获取子串的值时，只需要从开始处一直遍历，直到遇见空字符为止。

KMP算法

  回溯，有时候是好事，但有时候居然是坏事。如果现在有个很长很长的主串和一个不怎么长的模式串，让你去匹配这两个字符串，问主串中和模式串长得一模一样的最前面的子串在哪里。你会怎么做？最简单的暴力行为是，主串和模式串最前面对齐，一个字符一个字符进行核验，如果发现不一样的字符就停止当下核验，然后把模式串向后移动一个字符的位置，再从模式串最前面的位置开始重新进行一个字符一个字符核验，直到发现主串的这部分内容和模式串一模一样为止。这种暴力行为是包含回溯的。因为每次发现不一样的字符后都从模式串的开头开始而非中间，而且，主串中一定有一个下标或指针变量是会减小的。既然在模式串中间发现了不一样的字符那就表明前面的一样。但是暴力而为却没有将这部分信息利用起来。

  D.E.Knuth，J.H.Morris和V.R.Pratt这三个人提出，如果发现不匹配的字符，可以看在这一轮匹配中，前面主串和模式串相同的地方里面，前缀和后缀相同的部分。如果有前缀和后缀相同，我们就可以直接滑动模式串到前后缀重合的地方，而非只移动一个格子。那么究竟移动多少个格子呢？我们取相同的前缀和后缀中，最长的那个。如下图，相同的部分是"abcdbeabc"，现在有相同的前缀和后缀"abc"，那就移过去便是。要是相同的部分长这样"abcabdbfdyraabcab"，那这里就有相同的前后缀"ab"，但不是最长的，我们还是选取"abcab"最好。为什么要选最长的那个呢？因为那样的话模式串滑动得远，匹配次数少。

图中i为遍历主串的一个下标或者是指针，写代码时就是外层循环的循环变量。
而j是模式串中的，也就是内层循环的循环变量。

  设主串和模式串长度分别为m，n，因为KMP算法中i只向后走不向前走，不会回退，所以匹配次数有所减少。这方面的时间复杂度就成了m。而模式串中因为把重复的核验行为去除了，所以时间复杂度进一步降低。整体上的时间复杂度是O(m+n)，一下从平方级降到了线性级。

  然而在模式串中，当一个字符不匹配时，如何知道模式串内的当前比对字符应该前移到哪里呢？这里需要一个回退数组。在回退数组中，我们直接查表就知道应该让模式串回退到哪里了。

  例如，模式串"abcdbeabcg"有10个字符，对于开头的'a'，前面没有内容，也就没有公共前后缀，故回退数组中它的值是0，第2个字符'b'前面只有"a"，故亦为0，表示回退到模式串中最前面的字符。 （串的概念是首个字符编号为1的，但计算机中首个元素往往下标是0，此处是回退到自0开始计数的下标中去。）…… 第9个字符'c'前面是"abcdbeab"，前后有长度为2的公共前后缀"ab"。因此，一旦在模式串中这个字符'c'匹配出错，那么模式串的重新匹配中就不需要回退到一开始的字符'a'，而是自开头"ab"后面紧接着的'c'开始比较。 而开头"ab"后面紧挨着的'c'自0起的下标是2，于是第9个字符'c'的回退数组值为2。

  在上图例子中，检查到模式串的最后一个字符'g'时发现不匹配就得在模式串中回退。因为前方"abcdbeabc"中最后一个字符'c'的回退目的地为2，而开头的"ab"后面紧接着也是'c'， 这就延长了公共前后缀的一个字符之长度，接下来的比较只需从模式串开头"abc"后面紧挨着的'd'开始进行比较。所以模式串最后一个字符'g'的回退目的地为2+1=3。情况如下：

a	b	c	d	b	e	a	b	c	g
0	0	0	0	0	0	0	1	2	3

  另一个的字符串"abcababc"的情况则是：

a	b	c	a	b	a	b	c
0	0	0	0	1	2	0	2

  这种寻找是通过递推实现的：模式串中前两个字符回退目的地必为0，对于后面的内容，如果模式串中当前字符的前一个字符回退目的地不为0， 就看上一个回退目的地的字符和当前字符是否一样，一样则当前回退目的地取上一个回退目的地加1。除此之外的情况，则是将去寻找上一个回退目的地处的字符，它的回退目的地，在那里重新比较， 一样，则在那个下标上加1，不一样就继续向前，套娃式地找这个回退目的地的字符，反复找，直至二者相等。为什么要这样做呢？因为越是靠前的部分，越是回退阶数高的部分，重复性往往可以越强。

  这个回退数组在一些资料记载中也叫next数组，它记载了模式串中当前字符和主串不匹配时，需要将模式串的当前字符下标改为几。 KMP算法就是要先求出模式串的回退数组，然后开始和主串内容的匹配，如果模式串和主串的当前字符不相等，则按照回退数组回退，调整模式串的当前字符。

辛酸网 ©版权所有