1 |
String Superprimitivity test and LCS on the Reconfigurable Bus ModelChang, Jenn-Dar 24 July 2000 (has links)
Problems of some regularities in strings, such as repetition,
period, seed, square, etc., have been studied extensively
recently. Many algorithms have been proposed to solve these
problems in O(1) time complexity on an n imes n
reconfigurable bus model, where $n$ is the length of the given
string.
In this paper, we concentrate to solve problems of another form of
regularity, the string superprimitivity test problem and the
LCS (longest common subsequence) problem in strings on the
reconfigurable bus model. And we propose a O(log n) time
parallel algorithm to solve the string superprimitivity test
problem. We also review some algorithms for the LCS problem.
Further research is also given in this paper.
|
Page generated in 0.0782 seconds