algorithm - How do you check if one array is a subsequence of another?

Question

I'm looking to explore different algorithms, both recursive and dynamic programming, that checks if one arrayA is a subsequence of arrayB. For example,

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

thus, arrayA is indeed a subsequence of arrayB. 

I've tried a few different searches, but all I can seem to find is algorithms to compute the longest increasing subsequence.

Answer 1

Since you must match all elements of arrayA to some elements of arrayB, you never need to backtrack. In other words, if there are two candidates in arrayB to match an element of arrayA, you can pick the earliest one, and never retract the choice.

Therefore, you do not need DP, because a straightforward linear greedy strategy will work:

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;
}