0
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:)

4

2 回答 2

0

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

于 2012-04-05T15:35:14.353 回答
0

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

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

于 2012-04-05T15:18:44.210 回答