(This is a more detailed and precise version of https://stackoverflow.com/a/63914397/9459301.)
A pattern is an alternating sequence of literals, which match only themselves, and wildcards, which match zero or
more characters. For example, ab*c*de
is a pattern with starting literal ab
, interior literal c
,
and ending literal de
.
Two patterns p1 and p2 overlap if there is some string that they both match. We can compute whether they overlap in linear time as follows.