HBC19956[FJOI2015]带子串包含约束LCS问题题解

为你而来永不停止算法基础篇 2023-11-18 16:02:01 45 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

带有子串包含约束的最长公共子序列问题可以具体表述如下，给定2个长度分别为n和m的序列X和Y，以及一个子串包含约束集S， S中共有k个字符串S={S1,S2,…tn的子串是一个形如T’=t1+i…

带有子串包含约束的最长公共子序列问题可以具体表述如下。给定2个长度分别为n和m的序列X和Y，以及一个子串包含约束集S。 S中共有k个字符串S={S1,S2,…,Sk}，其中字符串Si的长度为li，1 ≤ i ≤ k。带有子串包含约束的最长公共子序列问题就是要找出X和Y的包含约束集S中所有字符串为其子串的最长公共子序列。例如，如果给定的序列X和Y分别为X=actaagacct, Y=gacctacctc，子串包含约束集S={ata, tact}，则子序列actacct是X和Y的一个无约束的最长公共子序列，而包含约束集S中所有字符串为其子串的一个最长公共子序列是atact 。在本题中请特别关注子串与子序列的区别。字符串T=t1…tn的子串是一个形如T’=t1+i…tm+i的字符串，其中，0 ≤ i，m+i ≤ n。例如，T=abcdefg，则bcd是T 的一个子串，而bce是T的一个子序列，但不是T的子串。设计一个算法，找出给定序列X和Y带有子串包含约束S的最长公共子序列。