QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[+4]

# 305. 最长公共相似子序列问题

Statistics

题目描述

X=x1x2Xn 是一个给定的基因序列。其中 xi{A,C,G,T},1in

对于一个基因序列 X,我们称它的 i 位移(1in)为 X 的后 i 位与 X 的前 ni 位拼接而成的字符串。一个基因序列的特征定义为它的字典序最小的位移。

对于两个基因序列,我们称它们相似当且仅当它们的特征相等。

最长公共相似子序列问题是要求对于给定的两个长度相同的基因序列 X=x1x2xnY=y1y2yn,计算其最长公共相似子序列的长度。

编程任务

对于给定的两个长度相同的基因序列 X=x1x2xnY=y1y2yn,计算其最长公共相似子序列的长度。

输入格式

输入的第一行包含一个正整数 n

接下来两行分别给出输入序列 X=x1x2xnY=y1y2yn。其中序列中每个元素均为 {A,C,G,T} 中的字母。

输出格式

输出一行一个整数表示答案。当不存在公共相似子序列时,输出 0

样例数据

样例输入

6
CCAGTA
ATAGTC

样例输出

4

子任务

对于 10% 的数据,n10

对于 40% 的数据,n300

对于 70% 的数据,n1000,保证数据随机生成。

对于 100% 的数据,n2000