Description最长后辍匹配指的是在一个单词中,一个任意非后辍的子串与后辍的最长匹配。 如单词banana,其最长后辍匹配为:b"ana"na和ban"ana"。(引号内的部分即为匹配的部分) 所以, 现在给你一个单词,仅包含小写字母a-z。请你求出它的最长后辍匹配。 一些其它的例子:
Solution这个题目考察了一下我们的知识迁移能力。 我们由最长后辍匹配不难想到最长前辍匹配。毕竟我们把字符串翻转一下,后辍就是前辍。 如果说我们对最长前辍匹配还是不熟悉的话,那么你一定对这个算法耳熟能详 —— K(看)M(毛)P(片)。 网上有好多对于KMP算法的解释,但是大多都过于详细。其实KMP从根本上说,字符串的最长前辍匹配。 以ananab为例。其最长前辍匹配数组为: (这里的最长前辍匹配与KMP的next数组并不完全一致,但原理是一样的) 我们可以看出,next[i]表示着以i为结尾位置的子串与前辍的最长匹配。 例如,prefix_match[4] = 2(第3个a)。说明前辍与以第3个a结尾的所有子串的最长匹配为"ana"(即[0..2])。 即:初始时后辍最后一个字符的位置为1,与其对应的前辍为0。 当前辍与后辍添加一个匹配时,更新后辍的最长前辍。 当前辍与后辍不能匹配时,后辍尝试使用次长的前辍,试图再次进行更新。 即然我们已经知道最长前辍的计算方法,那么最长后辍不过是多进行一次字符串翻转罢了。 |
|