计算字符串的所有子字符串中子序列的出现次数

问：

我想编写一个算法来计算字符串的所有子字符串中字符子序列的（不相交）出现次数。下面是一个示例。

字符串：“jabcohnnyjohnny”

子序列：“johnny”

包含子序列的子字符串：

jabcohnny
jabcohnnyj
jabcohnnyjo
jabcohnnyjoh
jabcohnnyjohn
jabcohnnyjohnn
jabcohnnyjohnny (2x)
abcohnnyjohnny
bcohnnyjohnny
cohnnyjohnny
ohnnyjohnny
hnnyjohnny
nnyjohnny
nyjohnny
yjohnny
johnny

答案：17

通过蛮力检查每个可能的子字符串非常简单，但我想要一个更有效的解决方案。我试图找出一种比 O（N^2） 时间复杂度更好的算法，其中字符串的长度为 N。我们可以假设子序列的长度很小且恒定，因此对于时间复杂性来说，这不是问题。

我注意到遍历每个可能的子字符串的蛮力方法重复了大量工作。例如，示例中的子字符串 1-6 都对子序列的同一实例进行计数。

我尝试使用动态规划来制定解决方案，基于查找字符串中子序列的出现次数的类似问题。不幸的是，我无法弄清楚如何解释所有子字符串，而不仅仅是从字符串开头开始的子字符串。

我也明白这个问题可以使用两指针或滑动窗口方法解决，但我也无法在这些方面取得太大进展。