kmp算法_joylnwang的专栏(2)

f(j) 0 1 1 1 2 3 4 5 1 2

我们可能考虑还是使用之前的笨方法来求出f(9)，但是且慢，利用之前的结果，我们还可以得到更多的信息。还是以pattern[8]为例。f(8) = 5，pattern[1...4]=pattern[4...7]，此时我们需要关注pattern[8]，如果pattern[8] != pattern[5]，那么在匹配算法如果匹配到pattern[8]才失败，此时就可以将输入字符target[n]与pattern[f(8)] = pattern[5]对齐，再向后依次执行匹配，所以此时的next[8] = f(8)（此平移的正确性，后面会作出说明）。而如果pattern[8] = pattern[5]，那么pattern[1...5]=pattern[4...8]，如果target[n]与pattern[8]匹配失败，那么同时也意味着target[n-5...n]!=pattern[4...8]，那么将target[n]与pattern[5]对齐，target[n-5...n]也必然不等于pattern[1...5]，此时我们需要关注f(5) = 2，这意味着pattern[1] = pattern[4]，因为pattern[1...4]=pattern[4...7]，所以pattern[4]=pattern[7]=pattern[1]，此时我们再来比较pattern[8]与pattern[2]，如果pattern[8] != pattern[2]，就可以将target[n]与pattern[2]，然后比较二者是否相等，此时next[8] = next[5] = f(2)。如果pattern[8] = pattern[2]，那么还需要考察pattern[f(2)]，直到回溯到模式串头部为止。下面给出根据f(j)求next[j]的递推公式：

如果 pattern[j] != pattern[f(j)]，next[j] = f(j);

如果 pattern[j] = pattern[f(j)]，next[j] = next[f(j)];

当要求f(9)时，f(8)和next[8]已经可以得到，此时我们可以考察pattern[next[8]]，根据前面对于next的计算方式，我们知道pattern[8] != pattern[next[8]]。我们的目的是要找到pattern[9]的包含前缀，而pattern[8] != pattern[5]，pattern[1...5]!=pattern[4...8]。我们继续考察pattern[next[5]]。如果pattern[8] = pattern[next[5]]，假设next[5] = 3，说明pattern[1...2] = pattern[6...7]，且pattern[3] = pattern[8]，此时对于pattern[9]而言，就有pattern[1...3]=pattern[6...8]，我们就找到了f(9) = 4。这里我们考察的是pattern[next[j]]，而不是pattern[f(j)]，这是因为对于next[]而言，pattern[j] != pattern[next[j]]，而对于f()而言，pattern[j]与pattern[f(j)]不一定不相等，而我们的目的就是要在pattern[j] != pattern[f(j)]的情况下，解决f(j1)的问题，所以使用next[j]向前回溯，是正确的。

现在，我们来总结一下next[j]和f(j)的关系，next[j]是所有满足pattern[1...k - 1] = pattern[(j - (k - 1))...j -1](k < j)，且pattern[k] != pattern[j]的k中，k的最大。而f(j)是满足pattern[1...k - 1] = pattern[(j - (k - 1))...j -1](k < j)的k中，k的最大。还是以上例的模式来说，对于第7个元素，其f(j) = 4, 说明pattern[7]的前3个字符与模式的前缀3相同，但是由于pattern[7] = pattern[4], 所以next[7] != 4。

通过以上这些，读者可能会有疑问，为什么不用f(j)直接作为kmp算法的跳转表呢？实际从程序正确性的角度讲是可以的，但是使用next[j]作为跳转表更加高效。还是以上面的模式为例，当target[n]与pattern[7]发生匹配失败时，根据f(j)，target[n]要继续与pattern[4]进行比较。但是在计算f(8)的时候，我们会得出pattern[7] = pattern[4]，所以target[n]与pattern[4]的比较也必然失败，所以target[n]与pattern[4]的比较是多余的，我们需要target[n]与更小的pattern进行比较。当然使用f(j)作为跳转表也能获得不错的性能，但是KMP三人将问题做到了极致。

我们可以利用f(j)作为媒介，来递推模式的跳转表next。算法如下：

inline void BuildNext(const char* pattern, size_t length, unsigned int* next) { unsigned int i, t; i = 1; t = 0; next[1] = 0; while(i < length + 1) { while(t > 0 && pattern[i - 1] != pattern[t - 1]) { t = next[t]; } ++t; ++i; if(pattern[i - 1] == pattern[t - 1]) { next[i] = next[t]; } else { next[i] = t; } } //pattern末尾的结束符控制，用于寻找目标字符串中的所有匹配结果用 while(t > 0 && pattern[i - 1] != pattern[t - 1]) { t = next[t]; } ++t; ++i; next[i] = t; }

程序中，9到27行的循环需要特别说明一下，我们发现在循环开始之后，就没有再为t赋新，也就是说，对于计算next[j]时的t，在计算next[j1]时，还会用得着。实际这时的t的就等于f(j)。还是以上例的目标串为例，当j等于1，我们可以得出t = f(2) = 1。使用归纳法，当计算完next[j]后，我们假设此时t=f(j)，此时第11～14行的循环就是要找到满足pattern[k] = pattern[j]的最大k。如果这样的k存在，对于pattern[j1]而言，其前k个元素，与模式的前缀k相同。此时的t1就是f(j1)。这时我们就要判断pattern[j1]和pattern[t](t = t1)的关系，然后求出next[j1]。这里需要初始条件next[1] = 0。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shenmilingyu/article-3601-2.html