序列"/>
【Java】用动态规划的方法查找最长公共子序列
最长公共子序列的概念
LCS是(Longest Common Subsequence)的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。
比如,对于char x[]="aabcd";有顺序且相互相邻的aabc是其子序列,有顺序但是不相邻的abc也是其公共子序列。即,只要得出序列中各个元素属于所给出的数列,就是子序列。
再加上char y[]="12abcabcd";对比出才可以得出最长公共子序列abcd。
区别于最长公共子串
最长公共子串是寻找两个或多个已知字符串最长的子串。与最长公共子序列的区别在于子序列不必是连续的,而子串却必须是。
现有问题如下:
从键盘中输入两个字符串数组序列,求出它们的最长公共子序列的个数。
比如:X:A
更多推荐
【Java】用动态规划的方法查找最长公共子序列
发布评论