the galil rule, in its original version, is only effective for versions that output multiple matches. it updates the substring range only on , i.e. a full match. a generalized version for dealing with submatches was reported in 1985 as the apostolico–giancarlo algorithm.