Flexible String

题意翻译

对于长度为 $n$ 的 $a$,$b$ 两个字符串，$a$ 初始最多含有 $10$ 个不同字母。你可以选择至多 $k$ 个不同字母，将 $a$ 中的这些字母替换为任意字母。 你需要求出经过上述操作后，$a,b$ 相同位置且相同字母的子串尽可能多。 数据范围：$1 \le t \le 10^4,1 \le n \le 10^5,0 \le k \le 10$。

题目描述

You have a string $ a $ and a string $ b $ . Both of the strings have length $ n $ . There are at most $ 10 $ different characters in the string $ a $ . You also have a set $ Q $ . Initially, the set $ Q $ is empty. You can apply the following operation on the string $ a $ any number of times: - Choose an index $ i $ ( $ 1\leq i \leq n $ ) and a lowercase English letter $ c $ . Add $ a_i $ to the set $ Q $ and then replace $ a_i $ with $ c $ . For example, Let the string $ a $ be " $ \tt{abecca} $ ". We can do the following operations: - In the first operation, if you choose $ i = 3 $ and $ c = \tt{x} $ , the character $ a_3 = \tt{e} $ will be added to the set $ Q $ . So, the set $ Q $ will be $ \{\tt{e}\} $ , and the string $ a $ will be " $ \tt{ab\underline{x}cca} $ ". - In the second operation, if you choose $ i = 6 $ and $ c = \tt{s} $ , the character $ a_6 = \tt{a} $ will be added to the set $ Q $ . So, the set $ Q $ will be $ \{\tt{e}, \tt{a}\} $ , and the string $ a $ will be " $ \tt{abxcc\underline{s}} $ ". You can apply any number of operations on $ a $ , but in the end, the set $ Q $ should contain at most $ k $ different characters. Under this constraint, you have to maximize the number of integer pairs $ (l, r) $ ( $ 1\leq l\leq r \leq n $ ) such that $ a[l,r] = b[l,r] $ . Here, $ s[l,r] $ means the substring of string $ s $ starting at index $ l $ (inclusively) and ending at index $ r $ (inclusively).

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line contains two integers $ n $ and $ k $ ( $ 1\leq n \leq 10^5 $ , $ 0\leq k\leq 10 $ ) — the length of the two strings and the limit on different characters in the set $ Q $ . The second line contains the string $ a $ of length $ n $ . There is at most $ 10 $ different characters in the string $ a $ . The last line contains the string $ b $ of length $ n $ . Both of the strings $ a $ and $ b $ contain only lowercase English letters. The sum of $ n $ over all test cases doesn't exceed $ 10^5 $ .

输出格式

For each test case, print a single integer in a line, the maximum number of pairs $ (l, r) $ satisfying the constraints.

输入输出样例

输入样例 #1

6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb

输出样例 #1

6
3
6
6
6
11

说明

In the first case, we can select index $ i = 3 $ and replace it with character $ c = \tt{d} $ . All possible pairs $ (l,r) $ will be valid. In the second case, we can't perform any operation. The $ 3 $ valid pairs $ (l,r) $ are: 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} $ ". In the third case, we can choose index $ 2 $ and index $ 3 $ and replace them with the characters $ \tt{c} $ and $ \tt{d} $ respectively. The final set $ Q $ will be $ \{\tt{b}\} $ having size $ 1 $ that satisfies the value of $ k $ . All possible pairs $ (l,r) $ will be valid.

**题目大意**：

给定两个长度为 $ n $ 的字符串 $ a $ 和 $ b $，字符串 $ a $ 最初最多包含 10 个不同的字母。你可以选择至多 $ k $ 个不同字母，并将 $ a $ 中的这些字母替换为任意字母。你的任务是使得经过上述操作后，$ a $ 和 $ b $ 在相同位置上有尽可能多的相同字母的子串。

**输入输出数据格式**：

**输入格式**：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 10^5 $，$ 0 \le k \le 10 $），分别表示字符串的长度和集合 $ Q $ 中不同字符的限制。
- 第二行包含一个长度为 $ n $ 的字符串 $ a $，其中最多有 10 个不同的字母。
- 第三行包含一个长度为 $ n $ 的字符串 $ b $。
- 所有字符串 $ a $ 和 $ b $ 仅包含小写英文字母。所有测试用例中 $ n $ 的总和不超过 $ 10^5 $。

**输出格式**：
- 对于每个测试用例，输出一行，包含一个整数，表示满足条件的整数对 $ (l, r) $ 的最大数量。

**输入输出样例**：

**输入样例 #1**：
```
6
3 1
abc
abd
3 0
abc
abd
3 1
xbb
xcd
4 1
abcd
axcb
3 10
abc
abd
10 3
lkwhbahuqa
qoiujoncjb
```

**输出样例 #1**：
```
6
3
6
6
6
11
```

**说明**：

- 在第一个样例中，我们可以选择索引 $ i = 3 $ 并将其替换为字符 $ c = \text{d} $。所有可能的整数对 $ (l,r) $ 都将有效。
- 在第二个样例中，我们不能执行任何操作。有效的整数对 $ (l,r) $ 有 3 个。
- 在第三个样例中，我们可以选择索引 2 和索引 3，并将它们分别替换为字符 $ \text{c} $ 和 $ \text{d} $。最终集合 $ Q $ 将是 $ \{\text{b}\} $，大小为 1，满足 $ k $ 的值。所有可能的整数对 $ (l,r) $ 都将有效。**题目大意**： 给定两个长度为 $ n $ 的字符串 $ a $ 和 $ b $，字符串 $ a $ 最初最多包含 10 个不同的字母。你可以选择至多 $ k $ 个不同字母，并将 $ a $ 中的这些字母替换为任意字母。你的任务是使得经过上述操作后，$ a $ 和 $ b $ 在相同位置上有尽可能多的相同字母的子串。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 10^5 $，$ 0 \le k \le 10 $），分别表示字符串的长度和集合 $ Q $ 中不同字符的限制。 - 第二行包含一个长度为 $ n $ 的字符串 $ a $，其中最多有 10 个不同的字母。 - 第三行包含一个长度为 $ n $ 的字符串 $ b $。 - 所有字符串 $ a $ 和 $ b $ 仅包含小写英文字母。所有测试用例中 $ n $ 的总和不超过 $ 10^5 $。 **输出格式**： - 对于每个测试用例，输出一行，包含一个整数，表示满足条件的整数对 $ (l, r) $ 的最大数量。 **输入输出样例**： **输入样例 #1**： ``` 6 3 1 abc abd 3 0 abc abd 3 1 xbb xcd 4 1 abcd axcb 3 10 abc abd 10 3 lkwhbahuqa qoiujoncjb ``` **输出样例 #1**： ``` 6 3 6 6 6 11 ``` **说明**： - 在第一个样例中，我们可以选择索引 $ i = 3 $ 并将其替换为字符 $ c = \text{d} $。所有可能的整数对 $ (l,r) $ 都将有效。 - 在第二个样例中，我们不能执行任何操作。有效的整数对 $ (l,r) $ 有 3 个。 - 在第三个样例中，我们可以选择索引 2 和索引 3，并将它们分别替换为字符 $ \text{c} $ 和 $ \text{d} $。最终集合 $ Q $ 将是 $ \{\text{b}\} $，大小为 1，满足 $ k $ 的值。所有可能的整数对 $ (l,r) $ 都将有效。