Task 3 - Fraud Detection

核心思路

1. 遍历所有块大小
• 假设签名长度 = L。
• 可能的块大小 S ∈ [1, L]。

2. 如何分组
• 对每个签名：
• 按大小 S 切分成块（最后不足 S 的部分 → 尾巴）。
• 尾巴必须相同，才能在同一组。
• 对块序列，用「循环最小表示」来作为标准形态，确保不同重排方式能映射到同一组。
• 组合键 = 尾巴 + 块序列的标准形态。

3. 计算可疑度分数
• 遍历所有分组，统计每组大小。
• 分数 = 所有组大小的连乘积。

4. 选择最佳结果
• 比较所有块大小对应的分数。
• 返回最大分数对应的 (S, 分数)。
• 如果有多个 S 结果相同，返回任意一个。

伪代码

• 初始化
• 获取签名长度 sign_length。
• 设置最佳块大小 best_block_size = 1。
• 设置最佳分数 best_score = 1。

• 遍历所有可能的块大小
• 从 1 到 sign_length：
• 建立空的哈希表 groups，用来分组。
• 对每个交易：
• 取出签名字符串 sign。
• 按 block_size 切分签名 → 得到若干块，放入 blocks（保持有序）。
• 记录尾巴部分（不足一个块的字符）。
• 生成分组键 key = 尾巴 + 块序列拼接结果。
• 在 groups 中：
• 如果没有这个键，初始化为 0。
• 然后 +1，表示该组里多一个签名。
• 计算当前分数
• 初始化 suspicion = 1。
• 遍历 groups 中每个组的大小，做乘积。
• 更新最优解
• 如果 suspicion > best_score：
• 更新 best_score。
• 更新 best_block_size。

• 返回结果
• 返回 (best_block_size, best_score)。