SP12714 FATAWY - Fatawy
题目描述
Fatawy 是近期在埃及备受欢迎的社交网站。用户在其个人主页上发布法特瓦（Fatwa），与粉丝分享自己的见解。每个人都可以重新发布一条法特瓦，并在发布前对其进行一定程度的修改。
Zezo 对他关注的一系列法特瓦进行了分析，想了解在某一天大家正在讨论的热门话题。他试图开发一个系统，从每条法特瓦中提取特征，每条法特瓦最多可以有 10 个特征，用大写字母表示。根据这个系统，他定义了法特瓦之间的关系：如果两条法特瓦 A 和 B 的最长公共子序列（LCS）的长度与各自长度的百分比都超过阈值 TH，那么认为这两条法特瓦属于同一个话题。如果法特瓦 A 与法特瓦 B 属于同一话题，而 A 也与 C 属于同一话题，那么 B 和 C 也属于同一话题。（详见示例 1）。
众所周知，Zezo 并不擅长编程和实现这个系统，因此他会提供每条法特瓦的特征向量，请你帮忙计算出当天不同话题的数量。
请注意：
- 最长公共子序列（LCS）是找到一组序列中最长的公共子序列的问题（通常只涉及两个序列）。值得注意的是，子串是字符串中的连续部分，而子序列则不是必须连续的。
### 输入格式
第一行是一个整数 T，表示测试用例的数量。接下来的每个测试用例开始于一行，包含两个整数 N 和 TH，分别表示某一天的法特瓦数量（1 ≤ N ≤ 500）和阈值百分比 TH（为 0 到 100 之间的整数但不包括0和100）。接下来的 N 行，每行包含一个只由大写字母组成的字符串 $F_i$，其中 1 ≤ 长度($F_i$) ≤ 10。
### 输出格式
对于每个测试用例，输出一行格式为 “Case #T:”，T 是测试用例的编号；接下来一行表示该天的热门话题数量。
### 示例
```
输入：
2
3 60
ABC
ABB
ACC
5 80
BCCBC
AAABB
CACBC
CABCB
ABCAB
输出：
Case #1:
1
Case #2:
2
解释：
(ABC, ABB) 的 LCS 长度为 2，ABC 的长度是 3，ABB 的长度也是 3，ACC 的长度是 3。
LCS 与 ABC 的长度比为 66.66%，大于或等于 60%，
LCS 与 ABB 的长度比也是 66.66%，大于或等于 60%，
所以 ABC 和 ABB 被视作同一话题。
同理，ABC 和 ACC 也是同一话题。因此，(ABC, ABB, ACC) 被视为同一话题。
```
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无