String matching (SM) problem is to find the occurrences of a pattern within a text. Avanable length don't care (VLDC) is a special symbol, not belonging to a finite alphabet∑ but in ∑*. Each VLDC in the pattern can match any substring in the text. Given arun-length coded text of length 2nover ∑ and a run-length coded pattern of length 2mover ∑*, this paper first presents anO(1) time parallel SM algorithm for run-lengthcoded strings with VLDCs on a reconfigurable mesh (RM) usingO(nm) processors.Consider the hardware limitation in VLSI implementation. In order to be suitable forVLSI modular implementation, a partitionable parallel algorithm on the RM withlimited processors is further presented. ForN展开▼
