Parallel finding all initial palindromes and periods of a string on reconfigurable meshes |
| |
| Authors: | K -L Chung H -N Chen |
| |
| Affiliation: | (1) Department of Information Management and Graduate Program of Information Engineering, National Taiwan University of Science and Technology, 43, Section 4, Keelung Rd., Taipei, Taiwan 10672, R.O.C.;(2) Department of Information Management, Van-Nung Institute of Technology, 63-1, Shuiwei, Chungli, Taoyuan, Taiwan 320, R.O.C. |
| |
| Abstract: | Given a string of lengthn, this short paper first presents anO(1)-time parallel algorithm for finding all initial palindromes and periods of the string on ann×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 VLSI implementation.
Prof. Chung was supported in part by the National Science Council of R. O. C. under contracts NSC87-2213-E011-001 and NSC87-2213-E011-003. |
| |
| Keywords: | Palindromes parallel algorithms periods reconfigurable mesh string processing VLSI |
| 本文献已被 SpringerLink 等数据库收录！ |
|
