2番目のアナグラムである1番目の文字列のすべてのアナグラムの部分文字列の数を確認します。

Question

この問題を解決するアプローチが必要です！

問題：2番目の文字列の任意のアナグラムに等しいように、1番目の文字列のすべての異なるアナグラムの中で、交差していない部分文字列のモジュロ10^9 + 7をマッチした数の小文字アルファベットを含む2文字列。

例：
1）列1： "ABC"、文字列2： "AB"
回答= 4
説明： 'ABC'、 'BAC'、 'C​​AB'、 'C​​BA' のすべての貢献1それぞれが一致します。

2）列1： "ABCAB"、文字列2： "AB"
回答= 40
説明：一致カウントは2であるため、文字列1 'ABABC' の一つの可能​​なアナグラム 'AB' であり、 ' AB 'であり、一方、' BABCA 'は「BA」または「AB」の1つの試合のみに貢献する。

制約：
N、M第一及び第二の文字列の長さである
N メートル

Iが関与事前計算最初の200の階乗を実行しようとしたアプローチモジュロ10^9 + 7を計算し、与えられた文字列から、文字列が持つ可能性のある最大交差パターン（mx）を計算し、p = 1からmxまでループし、正確にp交差していない部分文字列を含む最初の文字列の並び替え回数を計算する（すなわち、ストリング2）パターンである。

私がここで紛失しているアプローチはありますか？

1）string2のアナグラムの数を計算 - ここ

Answer 1

は、あなたが使用できる別のアプローチです。あなたは（O（1）で）そうする方法（例えばx）を得るために、順列と組み合わせをGoogleで行うことができます。

2）string2がstring2に与えることができる最大数を計算します。これは、文字列の文字がstring2で何度繰り返されたかを計算することによって実行できます。あなたの2番目の例のように、 'A'と 'B'は文字列2で2回繰り返すので、一度に多くのアナグラムを得ることができます。 注 -文字の周波数が一致しない場合は、最も低い数値を選択してください。同様に、ある文字列 'A'が3回繰り返され、 'B'が2回まで最大2つのアナグラムを得ることができるので、最低の繰り返し文字の頻度を取ることができます。

3）は順列の式を用いて回答を計算し、N1、N2は文字列1及び2 RESPの長さで文字列2 x*(n1-n2+1)の一方のみアナグラムと文字列1のアナグラムの

• 数combination-。 2つのアナグラムで
• - (n1- 2*n2+2)*x*x
• などなど