能治愈白癜风的医院 http://m.39.net/pf/bdfyy/bjzkbdfyy/串的存储结构也类似线性表，有两种，顺序存储和链式存储。串的顺序存储结构，也是用定长数组来定义的。数组长度是串长度的最大值，那么每个时刻串的实际长度怎么看呢？不需要遍历，而是将串长度存储在数组首端或末端，也有语言给串的末尾加上一个不计入串长的结束标记字符来表示串的结束。这样的顺序存储结构，在实用中并不适合大多数串，因为其有固定的长度限制。所以在计算机中有一个自由存储区——“堆”，可以实现串值存储空间的动态分配，它可由C的malloc()和free()函数来管理。链式存储结构中，需要考虑字符怎样存放在结点中。如果一个字符对应一个结点，那么就需要用大量的指针域，浪费很多空间。所以我们可以在一个结点中按情况放入多个字符，当最后一个结点未占满时，用特定的非串值字符补全。总的来说，串的链式存储结构不如顺序存储结构灵活、高效。现实中人们常常需要在主串中定位字串，类似于搜索关键字词句。这种操作叫做串的模式匹配，地位相当重要。朴素而一般的算法是这样的。将子串的首字符与主串的首字符匹配，此时将子串各字符与主串首字符及其后对应的字符依序进行一一匹配，如果完全一致，则匹配成功；若匹配到不一致字符，则再将子串首字符与主串第二字符进行匹配（也就是相对于主串后移一位），重复上述过程，……。最终可能匹配成功，也可能匹配失败。整个过程中，每次将子串相对于主串向后移一位，再对子串和主串对应的位置进行遍历，最好的情况是一开始子串还未向后移动就能与主串匹配成功，最坏则是每次匹配失败都是坏在子串最后一个字符。可以看出，较好的情况下O(n+m),最坏的情况下O((n-m+1)*m)（其中n是主串长度，m是子串长度）。这样看来，朴素的模式匹配算法效率比较低下，尤其是对于二进制字符串0和1重复比较多的情况。后来，有三位科学家发明了一种算法，可以大大避免重复遍历的情况，称为Knuth-Morris-Pratt算法，简称KMP算法。KMP算法的核心是，如果子串中有与某段首端字符序列（也就是包含首字符的序列，称为前缀）相重复的另一段字符序列（称为后缀），在匹配时子串就可以不用一步步向后相对移动了，而可以“跳动”。也就是说，当字符串移动到某个位置时，如果后面的重复序列也能和主串对应位置字符匹配上，那么如果这次子串对主串遍历匹配失败的话，前缀就可以直接移动到后缀当前的位置上（当然还是要带着整个子串一起移动），直接在这个新位置上再进行每个字符的匹配遍历。当然，由于前缀已经跳到了先前后缀匹配过的主串位置，所以前缀、后缀和此时主串相应的序列是完全一致的，这次对子串的遍历匹配就可以免过前缀，直接对比之后的字符即可。这下就大大简化了高重复性串的匹配流程。
图一KMP算法对高重复性字符串的模式匹配过程进行了优化
为了描述一个子串中每个字符的重复程度，我们定义了一个数组next。对于一个子串，设j为各字符的序号，k是非负整数变量，有对于j的next[j]函数，如下图。
图二next[j]函数定义
这个函数的长度就是子串的长度，这是因为j的取值范围。对于一个子串的每个字符，next函数都有一个值，取决于序列中字符的重复性，以及它的位置j。下一节我将详细解释这个函数。还有，这部分内容中所说的“子串”，大部分情况是指匹配时所用的“关键字词句”，如果模式匹配成功了，它就是主串的子串；而如果匹配失败了，它就不是主串的子串，这一点值得注意。预览时标签不可点收录于话题#个上一篇下一篇