问题描述

TDP 公司决定起诉 JCN 公司侵犯版权。为此，TDP 希望在 JCN 的代码库中找到侵权片段，并向选定的媒体代表展示。由于 TDP 已经解雇了所有技术人员，他们希望雇佣一名顾问，并在诉讼成功后支付报酬。为了证明你适合这个职位，你需要解决多个测试用例的问题。

输入

每个测试用例以一个正整数 $k$ 开始，表示需要找到的侵权片段数量。接下来的输入包括两个代码库：

1. 第一个代码库以 BEGIN TDP CODEBASE 开头，包含若干行，以 END TDP CODEBASE 结尾。
2. 第二个代码库以 BEGIN JCN CODEBASE 开头，以 END JCN CODEBASE 结尾。

注意：

• END TDP CODEBASE 不会出现在第一个代码库中。
• END JCN CODEBASE 不会出现在第二个代码库中。
• 最后一个测试用例后是一个包含 $0$ 的行。

输出

对于每个测试用例，输出：

1. 一行 CASE n，其中 $n$ 是测试用例编号。

2. 最多 $k$ 个侵权片段。每个片段应完全按照其在 JCN 代码库中的形式输出（包括换行符和空格），并在前面添加一行：

   INFRINGING SEGMENT m LENGTH l POSITION p
   

   其中：

   • $m$ 是该片段在测试用例中的编号。
   • $l$ 是片段的长度（字符数）。
   • $p$ 是片段在 JCN 代码库中的起始位置（从代码库开头计算的字符偏移量，从 $0$ 开始）。

   片段之间用空行分隔。

侵权片段的定义

• 代码库是一个字符序列。
• 侵权片段是 JCN 代码库中的一个非空连续字符序列，且该序列与 TDP 代码库中的某个连续字符序列完全相同。
• 侵权片段不能包含在更大的侵权片段中。
• 所有字符（包括空格和换行符）都需要考虑。

排序规则

• 按片段长度从大到小排序。
• 如果长度相同，按其在 JCN 代码库中的出现顺序排序。
• 如果侵权片段数量超过 $k$，只输出前 $k$ 个。

假设

• 每个代码库的字符数不超过 $50,000$。

示例输入输出

输入 1：

6
BEGIN TDP CODEBASE
the quick brown fox
jumps over the lazy dog.
so there!
END TDP CODEBASE
BEGIN JCN CODEBASE
now is the time for all
good men to come to the aid
of the party.
so there!
END JCN CODEBASE
100
BEGIN TDP CODEBASE
xyzzy
END TDP CODEBASE
BEGIN JCN CODEBASE
xyzzabczzyy
END JCN CODEBASE
0

输出 1：

CASE 1
INFRINGING SEGMENT 1 LENGTH 12 POSITION 64
.
so there!

INFRINGING SEGMENT 2 LENGTH 5 POSITION 6
 the 
INFRINGING SEGMENT 3 LENGTH 5 POSITION 42
o the
INFRINGING SEGMENT 4 LENGTH 5 POSITION 43
 the 
INFRINGING SEGMENT 5 LENGTH 5 POSITION 54
 the 
INFRINGING SEGMENT 6 LENGTH 3 POSITION 15
 fo

CASE 2
INFRINGING SEGMENT 1 LENGTH 4 POSITION 0
xyzz
INFRINGING SEGMENT 2 LENGTH 3 POSITION 7
zzy
INFRINGING SEGMENT 3 LENGTH 2 POSITION 10
y

数学公式说明

1. 片段长度 $l$：

   • 计算为片段中字符的总数，包括空格和换行符。
   • 例如，片段 the 的长度为 $5$（包括前后空格）。

2. 起始位置 $p$：

   • 从 JCN 代码库的第一个字符开始计算，偏移量从 $0$ 开始。
   • 例如，片段 the 的起始位置为 $6$，表示它是 JCN 代码库的第 $7$ 个字符（从 $0$ 开始计数）。