# BalticOI 2019 Day2 项链## 题目背景译自 BalticOI 2019httpboi2019eioeetasks Day2 T2 Necklacehttpboi2019eioeewp-contentuploads201905necklaceen_pdf## 题目描述Jill 和 Jane 是姐妹去年圣诞节他们每个人都得到了一串彩色珠子。我们可以将每种颜色描述为小写英文字母$t

思路

这道题可以通过比较两串彩珠的最长公共子序列来解决。假设 Jill 的彩珠串为 A，Jane 的彩珠串为 B。

首先，我们将 A 原封不动地复制一遍，得到 AA。然后我们将 B 倒序复制一遍，得到 BB。接下来，我们将 AA 和 BB 拼接起来，得到 AA+BB。

现在我们要找到 AA+BB 中最长的公共子序列，这个子序列就是 Jill 和 Jane 所能得到的最长项链。但是我们需要注意，这个最长公共子序列的长度可能会超过 A 和 B 的长度，因为 AA+BB 中的某些字符并不属于 A 或 B。

所以我们需要对最长公共子序列进行一些处理。首先，我们找到最长公共子序列的起始位置，即 AA+BB 中的某一个字符。然后我们记录该字符在 AA 和 BB 中的位置，再根据 AA 和 BB 的长度，计算出该字符在 A 和 B 中的位置。

最后，我们将最长公共子序列的长度除以 2，得到 Jill 和 Jane 所能得到的最长项链的长度。

算法

1. 读入 Jill 和 Jane 的彩珠串 A 和 B。
2. 复制 A 得到 AA，倒序复制 B 得到 BB。
3. 拼接 AA 和 BB 得到 AA+BB。
4. 在 AA+BB 中找到最长公共子序列的起始位置，并记录其在 AA 和 BB 中的位置。
5. 根据 AA 和 BB 的长度以及最长公共子序列的位置，计算出最长公共子序列在 A 和 B 中的位置。
6. 计算最长公共子序列的长度并除以 2，得到 Jill 和 Jane 所能得到的最长项链的长度。
7. 输出结果。

复杂度分析

由于我们只需要找到最长公共子序列的长度，所以算法的时间复杂度为 O(N^2)，其中 N 是彩珠串的长度。

代码实