题目描述

一个串的“子序列”是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。

我们说串 $t$ 是串 $s_1$ 和 $s_2$ 的公共子序列，当且仅当 $t$ 是 $s_1$ 的子序列且 $t$ 是 $s_2$ 的子序列。定义串 $s_1$ 和 $s_2$ 的相似度为它们最长公共子序列的长度。

现在给定一个文本串 $S$ 和一组模式串 $T[1], T[2], \dots, T[n]$，求 $T[i]$ 中和 $S$ 具有最高相似度的那个，然后输出最高的相似度。