考虑这个旋转操作,本质上就是把一个字符往左移动一些位。
如果两个字符串每个字符的数量相等,那么如果从左到右逐一归位必然可以构造出一组解,当然如果数量不同那肯定没法归位。
然后不难发现本质上就是一个匹配问题,我们固定一些 中的位置,这些位置必须满足在 中的相对顺序和在 中一样,只归位剩下的,不难发现必然也是一组解。
相当于我们现在要找一个类似 LCS 的东西。但是会发现它和 LCS 是有差别的直接拿 LCS 不太对。因为当有一个 中的位置和 中的一个位置 不匹配的时候,我们必须保证 中这个位置后面必须有一个 ,然后把 挪上来和这个 的位置匹配。也就是说,如果 中的 的个数小于当前 中的个数,那么我们不能在这里让 中的这个位置失配。