找到第一个字符串的所有字符串的子字符串的第二个字符串的计数

Question

需要一种方法来解决这个问题！

问题：给定两个包含小写字母的字符串计算第一个字符串的所有不同字符串中非相交子字符串的匹配模数10^9 + 7的匹配数目，以使它们等于任何第二个字符串的字符串。

实施例：
1）字符串1： “ABC”，字符串2： “AB”
回答= 4
说明： 'ABC'， 'BAC'， 'CAB'， 'CBA' 都有助于1这样匹配每个。

2）字符串1： “ABCAB”，字符串2： “AB”
回答= 40
说明：串1 'ABABC' 的哪个匹配计数为2的一个可能的字谜即 'AB' 和“ AB'，而'BABCA'只贡献一次'BA'或'AB'。

限制条件：
N，M是第一长度和第二串
Ñ 米

该方法我想这样做涉及预先计算第一200个阶乘以10^9 + 7为模，然后从给定的字符串计算该字符串可能有多少个最大非相交模式（mx），并从p = 1循环到mx，并计算包含恰好p个非相交子字符串的第一个字符串的重新排列次数（即字符串2）模式。

有没有不同的方法，我在这里失踪？

Answer 1

这里是另一种方法，你可以使用 -

1）计算字符串2的字谜游戏的数量。你可以谷歌排列和组合来得到一个方法来做到这一点（在O（1））（比如说x）。

2）最多计算string2可以产生多少个string1。这可以通过计算字符串字符在字符串2中重复的次数来完成。就像在你的第二个例子中，'A'和'B'在字符串2中重复两次，所以你一次最多可以得到字符。 注 -如果字符频率不匹配时选择最小数字。就像对某些字符串'A'重复三次，'B'重复两次，你最多可以得到2个字符，所以你可以重复最低字符的频率。

3）用置换的公式和组合 - 字符串1字谜的

• 数量只有一个字谜字符串2 x*(n1-n2+1)的计算答案在n1和n2是字符串1和2的RESP长度。
• 有两个字谜 - (n1- 2*n2+2)*x*x
• 等等