Partitionable bus-based string-matching algorithm for run-length coded strings with VLDCs

String matching (SM) problem is to find the occurrences of a pattern within a text, A variable length don't care (VLDC) is a special symbol, not belon ging to a finite alphabet Sigma but in Sigma*, Each VLDC in the pattern can match any substring in the text. Given a run-length coded text of length 2 n over Sigma and a run-length coded pattern of length 2m over Sigma*, this paper first presents an O(1) time parallel SM algorithm for run-length code d strings with VLDCs on a reconfigurable mesh (RM) using O(nm) processors. Consider the hardware limitation in VLST implementation. In order to be sui table for VLSI modular implementation, a partitionable parallel algorithm o n the RM with limited processors is further presented. For N < n and M < IM , the SM for run-length coded strings with VLDCs can be solved in O((X) ove r cap (Y) over cap) time on the RM using O(NM)(= O((nm)/((X) over cap (Y) o ver cap))) processors, where (X) over cap = [(n - 1)/(N - 1)] and (Y) over cap = [(m - 1 )/(M - 1)].