Optimal neural network algorithm for on-line string matching
Yiu-Wing Leung, Jiangshe Zhang, Zongben Xu · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · 1998
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.