看了好久才懂，我好菜啊……
题意：给两个字符串 \(a\) 与 \(b\)，对于 \(q\) 次询问，每次询问给出一个 \(x\)，求存在多少个位置使得 \(a\) 从该位置开始的后缀子串与 \(b\) 匹配的长度恰好为 \(x\)。
这题可以 Hash+二分 \(O(n\log n)\) 过，还有一个高端做法是扩展 KMP（然而并不会
正解的话，还是 KMP。但此题对 KMP 的理解还是要求很高啊。
对 \(b\) 求一遍 \(nxt\)，再求 \(a\) 的 \(f\)。那么根据定义，\(f_i=j\) 表示 \(a_{i-j+1\sim i}=b_{1\sim j}\)，换句话说，\(a\) 从 \(i-j+1\) 开始的后缀与 \(b\) 的匹配长度至少为 \(j\)。
由于我们只是求出了至少，但题目问的是精确值，那么做一个转换，开一个桶 \(cnt\)，\(cnt_i\) 表示匹配长度至少为 \(i\) 的位置有几个，那么对于每一个询问，答案就是 \(cnt_x-cnt_{x+1}\)。
求完 \(f\) 后，我们把它扔进桶里。
还没完，考虑一下到现在为止 \(cnt\) 里存了什么，我们发现现在的 \(cnt_i\) 存的位置个数并没有覆盖所有的情况，也就是说我们要做一个后缀和来覆盖这些情况。
如何做后缀和？根据 KMP 的性质，如果 \(a[i-j+1\sim i]=b[1\sim j]\)，那么 \(a[i-j+1\sim i-j+nxt[j]]=b[1\sim nxt[j]]\) 同样成立，并且中间的都不成立，也就是说，\(nxt[j]\) 是次选项。进一步地，\(nxt[nxt[j]],nxt[nxt[nxt[j]]],...\)都是满足条件的选项，这样我们的答案就得到了扩展并覆盖了所有情况。
所以我们倒序枚举 \(m\)，后缀和的递推式就是cnt[nxt[i]]+=cnt[i]。
本题真心很难理解（好像字符串题就没有好理解的），一定要多画图，把抽象描述形象化。
原文：https://www.cnblogs.com/wzzyr24/p/12114677.html