PARALLEL STRING MATCHING WITH K-MISMATCHES

被引:14
作者
GALIL, Z
GIANCARLO, R
机构
[1] TEL AVIV UNIV,DEPT COMP SCI,IL-69978 TEL AVIV,ISRAEL
[2] UNIV SALERNO,DEPT COMP SCI,I-84100 SALERNO,ITALY
关键词
COMPUTER SYSTEMS; DIGITAL - Parallel Processing;
D O I
10.1016/0304-3975(87)90042-9
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Two improved algorithms for string matching with k mismatches are presented. One algorithm is based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.
引用
收藏
页码:341 / 348
页数:8
相关论文
共 12 条
  • [1] Fischer M.J., 1974, SIAM AMS P, V7, P113
  • [2] AN EFFICIENT GENERAL-PURPOSE PARALLEL COMPUTER
    GALIL, Z
    PAUL, WJ
    [J]. JOURNAL OF THE ACM, 1983, 30 (02) : 360 - 387
  • [3] Galil Z., 1986, SIGACT News, V17, P52, DOI 10.1145/8307.8309
  • [4] FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS
    HAREL, D
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (02) : 338 - 355
  • [5] HERSHBERGER J, 1985, STANCS851050 STANF U
  • [6] Landau G. M., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P126, DOI 10.1109/SFCS.1985.22
  • [7] EFFICIENT STRING MATCHING WITH K-MISMATCHES
    LANDAU, GM
    VISHKIN, U
    [J]. THEORETICAL COMPUTER SCIENCE, 1986, 43 (2-3) : 239 - 249
  • [8] LANDAU GM, 1986, 18TH P ACM S THEOR C, P220
  • [9] SPACE-ECONOMICAL SUFFIX TREE CONSTRUCTION ALGORITHM
    MCCREIGHT, EM
    [J]. JOURNAL OF THE ACM, 1976, 23 (02) : 262 - 272
  • [10] Reif J. H., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P496, DOI 10.1109/SFCS.1985.9