从字符串对查找未知排列

Question

假设我有一堆字符串对，表示“before”和“after”值。为了给出一个简单的例子：

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

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

有没有关于这个问题的一些文献？此外，如果列表中的某些对精确匹配，是否会有“最可能”排列的概念？可以找到更复杂的排列，除了左右移动吗？

Answer 1

您需要知道graph theory和matching的基本概念。

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

“最有可能”的排列会更困难，它需要“最可能”的确切定义。你想满足尽可能多的配对吗？或更多匹配的字符是首选？

Answer 2

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

例如： abcd左转两个是cdab。 所以abcd与自身连接的是abcdabcd，通知cdab是一个子串。

我想检测一下，它确实是一个左边两个旋转，你可以检查子字符串是否从第三个字符开始。您可能需要检查其他几个案例，以确认它不是朝另一个方向旋转。