给你三个长度为$2n$的01串.现在要你找到一个长度最长为$3n$的01串,使得至少有两个$2n$的01串是这个串的子序列.
就很简单可以证明,$3n$的串一定可以得到.
假设一个$2n$的串是00000,另一个是11111.于是我们可以立刻发现,第三个串无论怎么构造和前面两个串的差异的最大值就是$n$.于是公共部分一定可以拿出$n$个来,剩下小于等于$n$的差异直接补上去就完事.
如果直接按照这个思路裸着做,要求两个串的最长公共子序列,就很麻烦.于是注意到这是一个01串.那么对于一个串,要么0多,要么1多.
我们就假设0多好了.既然是0多,那么我们把小于等于$n$的1,直接各自往里面插入不就好了.
比如001100和010100.首先搞出四个0.得到0000.然后把001100的1插进去就得到001100.再把010100的1插进去得到01011100.