KMP与最小覆盖子串
最小覆盖子串:对于某个字符串s,它的最小覆盖子串指的是长度最小的子串p,p满足通过自身的多次连接得到q,最后能够使s成为q的子串。
比如:
对于s="abcab",它的最小覆盖子串p="abc",因为p通过在它后面再接上一个p(即重叠0个字符),可以得到q="abcabc",此时s是q的子串。
对于s="ababab",它的最小覆盖子串为p="ab"。
根据KMP算法的next数组的定义,设字符串s的长度为n,则next[n] = next[n - 1],n-1为s的最后一位。
next[n]表明s[0,1,2,...,next[n]-1] == s[n-next[n],...,n-1],设这两段分别为s1和s2。
若s1和s2的长度之和小于s的长度,则说明s1和s2分别为不重叠的前缀和后缀,则最小覆盖子串必为s截去s2之后得到的前缀。
若s1和s2的长度之和大于等于s的长度,则最小覆盖子串也必为s截去s2之后得到的前缀。
以上两种情况都可以推出这个结论:最小覆盖子串是s的前缀,它的长度为n-next[n]。
我对KMP的一些理解(lyp点拨的):pre[i](或next[i])的实质是串str[1..i]的最长且小于i的“相等前、后缀”分别为str[1..pre[i]](前缀)与str[(i-pre[i]+1)..i](后缀),通俗讲就是:使str[1..i]前k个字母与后k个字母相等的最大k值。
KMP算法详解可见:
另外一个结论:
最小覆盖子串(串尾多一小段时,用前缀覆盖)长度为n-next[n](n-pre[n]),n为串长。
证明分两部分:
1-长为n-next[n]的前缀必为覆盖子串。
当next[n]<n-next[n]时,如图a,长为next[n]的前缀A与长为next[n]的后缀B相等,故长为n-next[n]的前缀C必覆盖后缀B;
当next[n]>n-next[n]时,如图b,将原串X向后移n-next[n]个单位得到Y串,根据next的定义,知长为next[n]的后缀串A与长为前缀串B相等,X串中的长为n-next[n]的前缀C与Y串中的前缀D相等,而X串中的串E又与Y串中的D相等……可见X串中的长为n-next[n]的前缀C可覆盖全串。
2-长为n-next[n]的前缀是最短的。
如图c,串A是长为n-next[n]的前缀,串B是长为next[n]的后缀,假设存在长度小于n-next[n]的前缀C能覆盖全串,则将原串X截去前面一段C,得到新串Y,则Y必与原串长度大于next[n]的前缀相等,与next数组的定义(使str[1..i]前k个字母与后k个字母相等的最大k值。)矛盾。得证!有人问,为什么Y与原串长大于next[n]的前缀相等?由假设知原串的构成必为CCC……E(E为C的前缀),串Y的构成必为CC……E(比原串少一个C),懂了吧!
最后得出结论:总长度-next[n].
code:
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-10-02-21.08#include#include #include #include #include #include #include #include #include