最长后辍匹配 Max suffix match

Description

最长后辍匹配指的是在一个单词中，一个任意非后辍的子串与后辍的最长匹配。

如单词banana，其最长后辍匹配为:b"ana"na和ban"ana"。（引号内的部分即为匹配的部分）

所以，MaxSuffixMatch("banana") = 3。

现在给你一个单词，仅包含小写字母a-z。请你求出它的最长后辍匹配。

一些其它的例子：

1. gosh 的最长后辍匹配为0

2. cpp 的最长后辍匹配为1。c"p"p & cp"p"

Solution

这个题目考察了一下我们的知识迁移能力。

我们由最长后辍匹配不难想到最长前辍匹配。毕竟我们把字符串翻转一下，后辍就是前辍。

如果说我们对最长前辍匹配还是不熟悉的话，那么你一定对这个算法耳熟能详 —— K（看）M（毛）P（片）。

网上有好多对于KMP算法的解释，但是大多都过于详细。其实KMP从根本上说，字符串的最长前辍匹配。

以ananab为例。其最长前辍匹配数组为：

+---+---+---+---+---+---+ 
| a | n | a | n | a | b |    
+-----------------------+                                                     
|-1 |-1 | 0 | 1 | 2 |-1 |  
+---+---+---+---+---+---+ 

（这里的最长前辍匹配与KMP的next数组并不完全一致，但原理是一样的）

我们可以看出，next[i]表示着以i为结尾位置的子串与前辍的最长匹配。

例如，prefix_match[4] = 2（第3个a）。说明前辍与以第3个a结尾的所有子串的最长匹配为"ana"（即[0..2]）。

void get_next(const string& istr) {
    memset(next, -1, sizeof(next));

    int n = istr.size();
    for (int pre = 0, suf = 1; suf < n; /* pass */) {
        if (istr[pre] == istr[suf]) {
            next[suf] = pre;
            pre++; suf++;
        } else if (pre == 0) {
            next[suf] = -1;
            suf++;
        } else {
            pre = next[pre - 1];
        }
    }
}

即：初始时后辍最后一个字符的位置为1，与其对应的前辍为0。

当前辍与后辍添加一个匹配时，更新后辍的最长前辍。

当前辍与后辍不能匹配时，后辍尝试使用次长的前辍，试图再次进行更新。

即然我们已经知道最长前辍的计算方法，那么最长后辍不过是多进行一次字符串翻转罢了。