最长公共子序列问题

题目描述

给定两个字符串s1s2...sn和t1t2,,,tn。求出这两个字符串最长的公共子序列的长度。字符串s1s2...sn的子序列可以表示为si1si2...sim(i1<i2<...<im)的序列

1<=n,m<=1000

输入

第一行 n,m

第二行，长度为n的序列s

第三行，长度为m的序列t

输出

一个数，最长公共子序列的长度

样例

提示

令mem[i][j]表示A的前i个字符与B的前j个字符中的最长公共子序列长度，边界为mem[i][0]=mem[0][j]=0

来源/分类