CF1778C Flexible String

你有一个字符串 $a$ 和一个字符串 $b$，它们的长度均为 $n$。字符串 $a$ 中最多有 $10$ 种不同的字符。你还有一个集合 $Q$，初始时 $Q$ 为空。你可以对字符串 $a$ 进行如下操作任意次： - 选择一个下标 $i$（$1\leq i \leq n$）和一个小写英文字母 $c$。将 $a_i$ 加入集合 $Q$，然后将 $a_i$ 替换为 $c$。 例如，设字符串 $a$ 为 "$\tt{abecca}$"。我们可以进行如下操作： - 第一次操作，如果选择 $i=3$ 且 $c=\tt{x}$，则字符 $a_3 = \tt{e}$ 会被加入集合 $Q$。此时，集合 $Q$ 变为 $\{\tt{e}\}$，字符串 $a$ 变为 "$\tt{ab\underline{x}cca}$"。 - 第二次操作，如果选择 $i=6$ 且 $c=\tt{s}$，则字符 $a_6 = \tt{a}$ 会被加入集合 $Q$。此时，集合 $Q$ 变为 $\{\tt{e}, \tt{a}\}$，字符串 $a$ 变为 "$\tt{abxcc\underline{s}}$"。 你可以对 $a$ 进行任意次数的操作，但最终集合 $Q$ 中不同字符的数量不能超过 $k$。在这个限制下，你需要最大化满足 $a[l,r] = b[l,r]$ 的整数对 $(l, r)$ 的数量（$1\leq l\leq r \leq n$）。这里，$s[l,r]$ 表示字符串 $s$ 从下标 $l$（包含）到下标 $r$（包含）的子串。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下。 第一行包含两个整数 $n$ 和 $k$（$1\leq n \leq 10^5$，$0\leq k\leq 10$）——两个字符串的长度和集合 $Q$ 中不同字符的最大数量。 第二行包含长度为 $n$ 的字符串 $a$。字符串 $a$ 中最多有 $10$ 种不同的字符。 最后一行包含长度为 $n$ 的字符串 $b$。 字符串 $a$ 和 $b$ 均只包含小写英文字母。所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一行一个整数，表示在满足约束条件下，最多有多少对 $(l, r)$ 满足条件。

在第一个样例中，我们可以选择下标 $i=3$ 并将其替换为字符 $c=\tt{d}$。所有可能的 $(l,r)$ 对都将有效。 在第二个样例中，我们无法进行任何操作。$3$ 个有效的 $(l,r)$ 对为： 1. $a[1,1] = b[1,1] = \tt{a}$， 2. $a[1,2] = b[1,2] = \tt{ab}$， 3. $a[2,2] = b[2,2] = \tt{b}$。 在第三个样例中，我们可以选择第 $2$ 个和第 $3$ 个下标，并分别将它们替换为字符 $\tt{c}$ 和 $\tt{d}$。最终集合 $Q$ 为 $\{\tt{b}\}$，大小为 $1$，满足 $k$ 的限制。所有可能的 $(l,r)$ 对都将有效。 由 ChatGPT 4.1 翻译