c++ - How to compare two patterns efficiently in C++

Question

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

In my definition pattern 2 is a subpattern of pattern 1, since (0,1) of pattern 2 is contained by (0,1)(2,4) of pattern 1 and (2,3)(4,5) of pattern 2 is contained by (2,3)(3,4)(4,5) of pattern 1.

What is appropriate and efficient algorithm to implement this comparison? Thanks:)

Answer 1

Trivial：pattern2 的每个字符出现在 pattern1 中，并且顺序相同。前面的一个简单检查是长度（模式2）<=长度（模式1），因此这是O（长度（模式1））。这是最优的，因为必须考虑所有字符。

Answer 2

概念上：计算pattern1和pattern2的最长公共子序列，并检查是否等于pattern2。

实际上：您想测试 pattern2 是否是 pattern1 的子字符串。这可以通过对两个字符串进行一次扫描来更快地完成。