有两个各自具有一种序结构的集合,如何寻找这两个集合的一种共同子集使得:
1、子集中元素的排列顺序能同时满足这两个集合上的序结构;
2、符合1的前提下,子集尽可能大
比如把两个字符串当做集合:
a="我不知道如何解决这个问题"
b="不知道我能否想出解决该问题的办法"
那么符合条件的所谓“最大公共偏序子集”就是:
"不知道解决问题"
稍微解释一下c怎么来的,所谓的序结构,比如a字符串的就是:“我”要排在“不”前面,“不”又要排在后面的其他字前面,字符串上这种覆盖每个字的一维的从左到右的可传导的顺序关系,就可以当做是a字符串所具有的一个序结构,同理b字符串也一样。
然后c在是a,b的公共子集的同时,c中的每一个元素,还要满足a,b上的顺序关系,比如开头的"我"和"不"字,虽然是a,b的共同元素,但是它们两个字在a中和在b中的先后顺序不一样,所以它们不能同时出现在c中。
就是这么回事吧,有点像是在找最长公共子串,也有点像求交集。
声明一下,标题中的“最大公共偏序子集”这个名字是我乱取的,只是为了简要概括题意而已,不过或许数学里真有这么个说法。
其实这里的集合,也不是严格数学定义的集合,可以当他是一个collection而不是set,也就是说,元素可重复。
请各位给点思路就好