algorithm - ある配列が別の配列のサブシーケンスであるかどうかを確認するにはどうすればよいですか?

Question

1 つの arrayA が arrayB のサブシーケンスであるかどうかをチェックする、再帰的プログラミングと動的プログラミングの両方のさまざまなアルゴリズムを調査しようとしています。例えば、

arrayA = [1, 2, 3] 
arrayB = [5, 6, 1, 7, 2, 9, 3]

thus, arrayA is indeed a subsequence of arrayB. 

私はいくつかの異なる検索を試みましたが、見つけることができるのは、最長増加部分列を計算するアルゴリズムだけです。

Answer 1

のすべての要素arrayAを のいくつかの要素に一致させる必要があるため、バックトラックarrayBする必要はありません。つまり、の要素に一致する候補が に 2 つある場合、最も古いものを選択でき、選択を取り消すことはありません。arrayBarrayA

したがって、単純な線形貪欲戦略が機能するため、DP は必要ありません。

bool isSubsequence(int[] arrayA, int[] arrayB) {
    int startIndexB = 0;
    foreach (int n in arrayA) {
        int next = indexOf(arrayB, startIndexB , n);
        if (next == NOT_FOUND) {
            return false;
        }
        startIndexB = next+1;
    }
    return true;
}