Parallel Finding All Initial Palindromes and Periods of a String on Reconfigurable Meshes

摘要

Given a string of length n, this short paper first presents an O(1)-time parallel algorithm for finding all initial palindromes and periods of the string on an n×n reconfigurable mesh (RM). Then, under the same cost (=time×the number of processors=O(n~2)), we provide a partitionable strategy when the RM doesn't offer sufficient processors; this overcomes the hardware limitation and is very suitable for LSI implementation.