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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0724100-122252 |
| Date | 24 July 2000 |
| Creators | Chang, Jenn-Dar |
| Contributors | Chang-Biau Yang, Yue-Li Wang, S.C. Tai |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0724100-122252 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0052 seconds