Optimal neural network algorithm for on-line string matching |
| |
Authors: | Yiu-Wing Leung Jiang-She Zhang Zong-Ben Xu |
| |
Affiliation: | Dept. of Comput. Sci., Hong Kong Baptist Univ., Kowloon. |
| |
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. |
| |
Keywords: | |
|
|