c++ - C++ で 2 つのパターンを効率的に比較する方法

Question

pattern 1: [(0,1)(2,4)] => [(2,3)(3,4)(4,5)] 
pattern 2: [(0,1)] => [(2,3)(4,5)]

私の定義pattern 2では、 は のサブパターンです。これはpattern 1、(0,1)ofが ofpattern 2に含まれ、ofが(0,1)(2,4)ofに含まれているためです。pattern 1(2,3)(4,5)pattern 2(2,3)(3,4)(4,5)pattern 1

この比較を実装するための適切で効率的なアルゴリズムは何ですか? ありがとう：）

Answer 1

概念的には、pattern1とpattern2の最長共通部分列を計算し、それがpattern2と等しいかどうかを確認します。

実際：pattern2がpattern1のサブストリングであるかどうかをテストしたいとします。これは、両方の文字列を1回スキャンすることでより高速に実行できます。

Answer 2

自明: pattern2 の各文字が pattern1 に同じ順序で表示されます。前もっての簡単なチェックは、長さ (パターン 2) <= 長さ (パターン 1) であるため、これは O (長さ (パターン 1)) です。すべての文字を考慮する必要があるため、これが最適です。