KMP+DP+矩阵乘法优化。
设DP[i][j]为长度为i的主串已成功匹配到模版串末尾j位（主串不包括模版串）的情况总数。，则Ans=∑DP[n][i](0<=i<=l-1)
接下来我们可以发现DP转移方程可以用一个矩阵来实现，于是用KMP求出DP转移矩阵，然后进行矩阵快速幂，O(logn*m*m)。
本文共 202 字，大约阅读时间需要 1 分钟。
KMP+DP+矩阵乘法优化。
设DP[i][j]为长度为i的主串已成功匹配到模版串末尾j位（主串不包括模版串）的情况总数。，则Ans=∑DP[n][i](0<=i<=l-1)
接下来我们可以发现DP转移方程可以用一个矩阵来实现，于是用KMP求出DP转移矩阵，然后进行矩阵快速幂，O(logn*m*m)。
转载于:https://www.cnblogs.com/NanoApe/p/4396728.html