| 摘要 |
<p>The invention concerns a fast search method in a programmable controller of a pattern P in text T formed with n elementary signs, the pattern P being an ordered set of symbols capable of defining either a list of signs, or a bounded jump recorded as x(a,b), the pattern scanning the text in search of a match, the steps of the process being represented by a graph consisting of a succession of states Si and the links between said states, the status of a state i indicating the result of the search for matching the position i being stored in a bit di of a storage area D. The invention is characterised in that, for a bounded jump x(a,b), it consists in generating b states and links and b-a transitions ε and in executing at least a step which consists in generating storage areas l and F, which are initialized in accordance with the transitions, and the storage zone D is modified by D = D &verbar; ( (F - (D & l) ) & ∩ F). The search can be carried out forwards or backwards.</p> |
