c++ - 如何测试一个序列是否符合给定模式中的另一个序列？

Question

下面描述的算法叫什么名字？

描述:

如何测试一个序列是否符合给定模式中的另一个序列？

例如:

The pattern: the number appears in the same order.


bool isOrderValid(vector<int>& mainVec, vector<int>& subVec) {
    // how to implement this function?
}

test#1: isOrderValid({1, 2, 3, 4}, {2, 4}); // should return true
test#2: isOrderValid({1, 2, 3, 4}, {4, 2}); // should return false

解释:

测试 #1:子序列为 2、4；在主序列中，2出现在4之前，所以顺序是正确的。

测试 #2:子序列是 4, 2；但是在主序列中，4出现在2之后，所以顺序不正确。

注意:两个数组中可能存在重复项。例如:

isOrderValid({3, 6, 3, 1, 2, 3}, {3, 1, 3}); // should return true

Answer 1

这可以很简单地实现(我在这里使用函数对象):

class base_pattern_matcher{
    public:
        virtual bool operator()(const vector<int>& a , const vector<int>& b) = 0;
}

class in_order_pattern_matcher : public base_pattern_matcher{
    public:
        bool operator()(const vector<int>& a , const vector<int>& b){
            vector<int>::iterator iter_a = a.begin() , iter_b = b.begin();

            while(iter_b != b.end() && iter_a != a.end()){
                if(*iter_b == *iter_a)
                    //we found an occurence in a that matches the searched element in b
                    //--> search for the next element
                    iter_b++;

                 //check if the next element matches the searched element
                 iter_a++;
            }

            //we have found all elements of b in the given order
            return iter_b == b.end();
        };
}

isOrderValid(const vector<int>& a , const vector<int>& b , const base_pattern_matcher& matcher){
    return matcher(a , b);
}