從字符串對查找未知排列

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是一個子串。

我想檢測一下，它確實是一個左邊兩個旋轉，你可以檢查子字符串是否從第三個字符開始。您可能需要檢查其他幾個案例，以確認它不是朝另一個方向旋轉。