算法思路

• 提取KMP的性质，假如我们有两个串分别是A,B A是主串， B是匹配串，那么先把B做一遍KMP， 再由B向A做一遍字符串匹配，那么当A[i]匹配到B[j]的时候，就表明A[i - j + 1 ~ i] == B[1 ~ j],就仅仅这些吗？当然不是，A[i - ne[j] + 1~i] == B[1~ne[j]] A[i - ne[ne[j]] + 1~i] == B[1 ~ ne[ne[j]]] …知道j = 0 因此我们就可以用f[j] 表示A至少匹配B长度为j的数量， 当然对于每一个f[j] ++ 都应该操作一遍

while(j)f[ne[j]] ++;//但是这样复杂度太高了我们接受不了

• 怎么优化呢？ 对于每一个j 都有对应的 ne[j] ne[ne[j]] … 可以发现它相当于一个拓扑图，因此每次做完f[j] ++ 的时候我们先不管f[ne[j]] 最后倒着循环一遍即可

for(int i = m; i; i --)f[ne[i]] += f[i];

• 答案要求的是恰好匹配的x的数量， 而我们的数组存储的是至少为x的数量，因此答案就是f[x] - f[x + 1];