从字符串对中查找未知排列

Question

假设我有一堆字符串对，代表 "before" 和 "after" 值。举个简单的例子：

 aaaabbbb -> aabbbbaa
 abbbbbbb -> bbbbbbab
 aaabbbaa -> abbbaaaa
 cccccccc -> cccccccc

我如何确定一种可能的排列可能是 [ 6, 7, 0, 1, 2, 3, 4, 5 ]，或者换句话说，所有字符都向左旋转了两个空格？

有没有关于这个问题的文献？另外，如果列表中的某些对不完全匹配，是否会有 "most likely" 排列的概念？除了左右移动，还能找到更复杂的排列吗？

Answer 1

string rotation problem 的常见解决方案是将原始字符串与其自身连接起来，并检查测试字符串是否为子字符串。

例如： abcd 向左旋转二位是cdab。所以 abcd 与自身连接是 abcdabcd，注意 cdab 是一个子字符串。

我想检测它正好是向左旋转两个，你可以检查子字符串是否从第三个字符开始。您可能需要检查其他一些情况，以确认它不是朝另一个方向旋转。

Answer 2

您需要了解 graph theory and matching 的基本概念。

假设before的每个位置是左节点，after的每个位置是右节点。对于左侧位置 i 和右侧位置 j，从左侧节点 i 到右侧节点 j 连接一条边，当且仅当 x[i] 等于 y[j] 在所有对 x -> y 中。那么问题就变成了找到这个二分图的完美匹配，这是一个已解决的问题。

"most likely" 排列会更难，它需要 "most likely" 的精确定义。您想满足尽可能多的对吗？或者更多匹配的字符是首选？

Find unknown permutation from string pairs