string - 配列を比較して、一致するすべてのサブ配列を見つけます

Question

元の配列の両方に表示される長さ 2 以上のすべてのサブ配列を見つけるために、2 つの数値配列 (重複なし) を比較したいと考えています。

これを実装する最も効率的な方法を探しています。

Answer 1

これは、 Longest Common Substring Problemを思い起こさせます。wiki ページを読んでください。問題の適切な説明、適切な参照、さらには疑似コードもあります。これを解決するには、接尾辞ツリーと動的計画法の 2 つの方法があります。サフィックス ツリーはより効率的なソリューションのように見えますが、実装によってはより複雑になる場合があります。

動的計画法に慣れていない場合は、それを読んでください。あなたの問題とLongest Common Substringの唯一の違いは、一意の整数の配列があることですが、ここでは文字列に繰り返し文字がありました。

あなたはそれを有利に利用するかもしれませんが、大幅な効率改善は得られないと思います。