文字列のペアから未知の順列を見つける

Question

「前」と「後」の値を表す一連の文字列ペアがあるとします。簡単な例を与えるために：私は1つの可能な順列[6、7、0、1、2、3、4、5]、または他の言葉であってもよいことを決定する方法を

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

を、すべての文字がありました2つのスペースで左に回転しましたか？

この問題に関する資料はありますか？また、リスト内の一部のペアが正確に一致しない場合、「最も可能性の高い」置換という概念がありますか？左と右にシフトする以外に、より多くの順列が見つかることがありますか？

Answer 1

graph theoryとmatchingの基本的な概念を知る必要があります。

beforeの各位置は左ノードであり、afterの各位置は右ノードであるとします。 左の位置iと右の位置jでは、すべてのペアでx [i]がy [j]に等しい場合にのみ、左ノードiから右ノードjにエッジを接続します。x -> y この問題は、この2部グラフの完全な一致を見つけることになり、これは解決された問題です。

「可能性が最も高い」置換ははるかに難しく、「最も可能性が高い」という正確な定義が必要です。できるだけ多くのペアを満足させますか？それ以上の文字が好きですか？

Answer 2

string rotation problemの一般的な解決策は、元の文字列を連結し、テスト文字列が部分文字列かどうかを確認することです。

例： abcd左に2つはcdabです。 したがって、abcdはそれ自身と連結されています。abcdabcdです。通知cdabは部分文字列です。

正確には左に2つ回転していることを検出すると仮定して、部分文字列が3番目の文字から始まるかどうかを確認できます。あなたはそれが他の方向の回転ではないことを確認するためにいくつかの他のケースをチェックする必要があるかもしれません。