title: Optimal neural network algorithm for on-line string matching.
abstract: We consider an online string matching problem in which we find all the occurrences of a pattern of m characters in a text of n characters, where all the characters of the pattern are available before processing, while the characters of the text are input one after the other. We propose a space-time optimal parallel algorithm for this problem using a neural network approach, This algorithm uses m McCulloch-Pitts neurons connected as a linear array. It processes every input character of the text in one step and hence it requires at most n iteration steps.
authors.affiliation: Dept. of Comput. Sci., Hong Kong Baptist Univ., Kowloon.
authors.forename: Y W
authors.initials: YW
authors.lastname: Leung
authors.forename: J S
authors.initials: JS
authors.lastname: Zhang
authors.forename: Z B
authors.initials: ZB
authors.lastname: Xu