之前写kmp的时候只是硬记了next数组的求法，今天重温了一下，发现最大前缀后缀这么理解也是可以的，就来写它一波~~~
首先来理解一下前缀和后缀的定义，空口无凭，我先举个栗子：
src：abcdefg
prefix:a ab abc abcd abcde abcdef
suffix:g fg efg defg cdefg bcdefg
有了这个定义，接下来说一个字符串的最大前缀后缀就好说了，一个字符串的最大前缀和最小后缀就是指其完全相同的前缀和后缀里面，最长的那个，比如：abcdab的最大前缀后缀就是ab
kmp算法可以通过先求解一个lps数组来求解next数组，其中lps数组中的每一项lps[i]表示的是pattern串的子串[0，i]的最大前缀后缀，其求解代码如下：
-
void get_lps(string &pattern, int len, vector<int> &lps){
-
for(int i=0;i<len;i++)lps[i]=0;
-
int suffix=1;
-
int prefix=0;
-
while(suffix < len){
-
if(pattern[prefix]==pattern[suffix]){
-
lps[suffix]=++prefix;
-
suffix++;
-
}else if(prefix){
-
prefix = lps[prefix-1];
-
}else
-
suffix++;
-
}
-
}
这样求解出来的lps向右移动一个位置，并用-1补充首位置，求得的即是kmp算法中的next数组了~~~
阅读(2768) | 评论(0) | 转发(0) |
