题意:
求一个字符串的所有前缀串的匹配次数之和.
思路:
首先仔细思考: 前缀串匹配.
n个位置, 以每一个位置为结尾, 就可以得到对应的一个前缀串.
对于一个前缀串, 我们需要计算它的匹配次数.
k = next [ j ]
表示前缀串 Sj 的范围内(可以视为较小规模的子问题), 前缀串 Sk 是最长的&能够匹配两次的前缀串.
这和我们需要的答案有什么关系呢?
题目是求所有前缀串的匹配次数之和, 那么可以先求前缀串 Si 在整个串中的匹配次数, 再加和.
到此, 用到了两个"分治", 一是将大规模的问题减小为小规模的问题, 二是将询问的最终结果拆分......
阅读全文