SUBSTRING SEARCHING METHOD

摘要

A substring searching method is disclosed for locating within a character string (11), a substring that matches a given character pattern (12) of one or more characters, the characters making up the string and pattern being taken from the same character set. The method involves a preliminary phase in which a respective possible-match record (31) is formed for each character of the character set, this record indicating for each of the N last positions as the pattern is notionally moved up to the character associated with the record, to align the start of the pattern with the character, whether the character matches the corresponding character of the pattern. During a subsequent phase of the substring search method, the pattern (12) is notionally shifted along the string being searched (11) and at each position, a test is carried out one character at a time, to ascertain if the substring aligned with the pattern (12) matches the latter; whenever a character test indicates a mismatch, the pattern is shifted to a new position. The testing for a character match is effected by combining the possible match record (31) of a character of the substring being examined. With a current shift mask (50) that indicates the current state of knowledge concerning possible match positions, this combining operation involving forming an intermediate translated mask (51). The resultant new current shift mask (52) not only indicated whether a match is possible at the current position in view of the presence of the examined character, but also the amount by which the pattern should be shifted if a mismatch is indicated.