The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.5 / (1996))
Parallel Suffix-Prefix-Matching Algorithm and Applications
Zvi M. Kedem. Gad M. Landau, Krishna V. Palem,
Pages. 998-1023
Abstract
Contents 1. Introduction
1.1. Significant results in this paper
1.2. Previous work
2. An optimal-speedup algorithm for the s-p-matching problem
2.1. Computing characteristics and thereby deriving $\delta$
2.2. A simple suboptimal algorithm
2.3. Characterizing prefixes efficiently
2.4. The optimal algorithm
3. Applying the s-p matching algorithm
3.1. Multiple s-p-matching problems
3.2. String matching
3.3. Multipattern string matching
3.4. Multitext/muptipattern problem
3.5. Multidimensional pattern matching
3.6. The pattern-occurrence detection
3.7. On-line string matching
4. Conclusions
Key words mortized complexity, CRCW PRAMs, multidimensional pattern matching, parallel algorithms, pattern-matching automaton, speedup, string matching.
Mathmatical Subject Classification 68P99, 68Q10, 68Q22, 68Q25, 68