题目描述

一家刚成立的侦探事务所希望通过比较被改动前后的消息，找出其中仍然相同的内容。请帮助他们求出两条消息之间最长的单词匹配长度。

将每条消息中的标点符号等非字母数字字符视为分隔符，把消息拆分成一个个单词。连续的英文字母或数字属于同一个单词。

从两条消息的单词序列中，各选出若干单词，保持它们原来的先后顺序，但不要求连续。如果选出的单词依次完全相同，就构成一次匹配。请计算最多可以匹配多少个单词，即两个单词序列的最长公共子序列长度。

单词比较区分大小写。

输入格式

输入包含多组数据，读到文件结束为止，不给出数据组数。

每组数据占连续的两行，分别表示两条消息。行中可能包含空格、标点符号，也可能是空行。

必须完整读取每一行，不能跳过空行；空行同样属于当前这组数据。

输出格式

每组数据输出一行。先输出组号，组号从 $1$ 开始，按宽度为 $2$ 右对齐，然后输出英文句点和一个空格。

• 如果两条消息中至少有一条是空行，随后输出 Blank!。
• 否则，随后输出 Length of longest match: k，其中 k 是最长公共单词子序列的长度。

没有可匹配的单词时，长度为 $0$。只包含空格或标点的非空行，不属于这里所说的空行。

输入样例 #1

This is a test.
test
Hello!

The document provides late-breaking information
late breaking.

输出样例 #1

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 2

样例解释 #1

第一组中两个单词序列都含有 test，最长匹配长度为 1。第二组的第二行为空行，因此输出 Blank!。第三组中的连字符是分隔符，late 和 breaking 可以依次匹配，长度为 2。

输入样例 #2

red,blue;green
blue red green

输出样例 #2

 1. Length of longest match: 2

样例解释 #2

第一条消息拆分为 red blue green，第二条为 blue red green。可以匹配 red green 或 blue green，长度都是 2。

输入样例 #3

A a A
a A a
abc def
xyz

输出样例 #3

 1. Length of longest match: 2
 2. Length of longest match: 0

数据范围

每条消息不超过 $1000$ 个字符。

每个单词的长度小于 $20$。

输入可能包含多组数据。

来源

洛谷 UVA10100 · 原题