P16653 [GKS 2018 #F] Common Anagrams

Ayla 有两个字符串 $A$ 和 $B$，长度均为 $L$，每个字符串均由大写英文字母组成。她想知道 $A$ 中有多少个不同的子串，可以作为 $B$ 的某个异序词子串出现。更正式地说，她想要统计不同的有序对 $(i, j)$ 的数量，其中 $0 \le i \le j < L$，使得 $A$ 中从第 $i$ 个字符到第 $j$ 个字符（包含两端）构成的字符多重集与 $B$ 中某个长度为 $(j - i + 1)$ 的连续子串的字符多重集相同。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $L$，表示字符串的长度。随后两行各包含一个长度为 $L$ 的字符串，依次为字符串 $A$ 和 $B$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Ayla 所求的答案，如上所述。

在样例 #1 中，$L = 3$，$A = \text{ABB}$，$B = \text{BAB}$。$A$ 共有 $6$ 个子串： * `A`：子串 `A` 在 $B$ 中（平凡地）是一个异序词。 * `B`：子串 `B` 在 $B$ 中（平凡地）是一个异序词。 * `B`：子串 `B` 在 $B$ 中（平凡地）是一个异序词。 * `AB`：子串 `AB` 在 $B$ 中（平凡地）是一个异序词。 * `BB`：在 $B$ 中不存在对应的异序词子串。 * `ABB`：子串 `BAB` 在 $B$ 中是一个异序词。 总共有 $5$ 个子串在 $B$ 中存在对应的异序词子串，因此答案为 $5$。 在样例 #2 中，注意它与样例 #1 相同，只是交换了 $A$ 和 $B$。这导致答案变为 $6$！ 在样例 #3 中，注意 $A$ 中的子串 `CAT` 在 $B$ 中有对应的异序词子串 `TAC`。即使这两个子串在各自的字符串中位于不同位置，该子串仍然被计入。 在样例 #4 中，注意尽管 $A$ 中的子串 `SUB` 在 $B$ 中有多个对应的异序词子串，但它只被计数一次。 在样例 #5 中，注意 $A$ 的每个子串都在 $B$ 中有对应的异序词子串，因此答案为 $10$。 ### 限制条件 $1 \le T \le 100$。 $1 \le L \le 50$。 **小数据集（测试集 1 – 可见）** 两个字符串 $A$ 和 $B$ 仅由字符 `A` 和 `B` 组成。 **大数据集（测试集 2 – 隐藏）** 无额外限制。 翻译由 DeepSeek V4 Pro 完成