一个序列中去掉若干(也可以不去掉)元素剩下的部分称为其子序列。对于给定的序列X = <x1,x2,…,xm>,称序列Z = <z1,z2,…,zk>为X的一个子序列,仅当在X中存在一个递增序号序列<i1,i2,…,ik>,对所有的j(1,2,…,k)满足 xij= zj。例如,Z = <a,b,f,c>是X = <a,b,c,f,b,c> 的一个子序列,X中相应的序号序列为 <1,2,4,6>。要求输入两个字符串,求它们的最长公共子序列(最长公共子串)的长度。
输入格式:
测试数据有多组,处理到文件尾。对于每组测试,输入两个不包含空格的字符串。
输出格式:
对于每组测试,输出最长公共子串的长度。
输入样例:
abcfbc abfcab
abcbdbebfbgb achhdkfkkg
abcfbcabbab abfcababcbbbb
输出样例:
4
5
8
出处:
HDOJ 1159
参考代码
#include <stdio.h>
#include <string.h&