You could for example implement the criteria using these two rules:

1. A string is a true substring of another if the other string starts with something else
2. A string is a true substring of another if the other string ends with something else

Then you only need to find out how to construct an "or" condition for regular expressions and find implementations for "starts with", "ends with" and "something else".

See perlre for ideas on how to implement these.