String-matching with left-to-right networks

String matching is the process of searching for optimal alignment of two strings. In its more general form, the prototype string is replaced by a model representing multiple prototypes at the expense of an increase in computation complexity. The authors present a dynamic programming algorithm for models in the form of left-to-right networks, that is, directed graphs which may contain self-loops but not cycles; each vertex may represent one or more symbols including the empty symbol. The algorithm is extended to incorporate non-negative edge costs such as transition probabilities. The computation complexity in the number of edges and the length of the string.