DOI: 10.1145/321941.321946. A Space-Economical Suffix Tree Construction Algorithm

A Space-Economical Suffix Tree Construction Algorithm

10.1145/321941.321946

Crossref journal-article

Association for Computing Machinery (ACM)

Journal of the ACM (320)

Abstract

A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.

Bibliography

McCreight, E. M. (1976). A Space-Economical Suffix Tree Construction Algorithm. Journal of the ACM, 23(2), 262â272.

Authors 1

Edward M. McCreight (first)

References 8 Referenced 1,011

AHO , A V ., HoPcaoPr, J.E., AND ULLMAN , J.D. The Design and Analysis of Computer Agorithms . Addison-Wesley , Reading, Mass ., 1974 , Ch 9, pp. 317 - 361 . AHO, A V., HoPcaoPr, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Agorithms. Addison-Wesley, Reading, Mass., 1974, Ch 9, pp. 317-361. / The Design and Analysis of Computer Agorithms by AHO A V (1974)
KIMBALL , R B . A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh , Pa. , April 1974 . KIMBALL, R B. A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh, Pa., April 1974. / Pa. by KIMBALL R B (1974)
KNUTH , D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass , 1973 , Ch. 6 . 3 , pp. 490 - 493 . KNUTH, D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass, 1973, Ch. 6.3, pp. 490-493. / Ch. by KNUTH D.E. (1973)
KSUTH , D.E Pattern matching in strings. Unpub. lecture notes , Trondheim , Norway , May 1973 . KSUTH, D.E Pattern matching in strings. Unpub. lecture notes, Trondheim, Norway, May 1973. / Trondheim by KSUTH D.E (1973)
KNUTH , D.E. , MORRIS , J.H. JR ., AND PRATT , V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford , Calif. , Aug. 1974 . KNUTH, D.E., MORRIS, J.H. JR., AND PRATT, V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford, Calif., Aug. 1974. / Calif. by KNUTH D.E. (1974)
PRATT , V R . Applications of the Weiner repetition finder. Unpub. paper , Cambridge , Mass ., May 1973 ; rev Oct. 1973 PRATT, V R. Applications of the Weiner repetition finder. Unpub. paper, Cambridge, Mass., May 1973; rev Oct. 1973 / Applications of the Weiner repetition finder. Unpub. paper by PRATT V R (1973)
10.1145/360980.360995
WEINER , P. Linear pattern matching algorlthms . Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory , pp. 1 - 11 . 10.1109/SWAT. 1973 .13 WEINER, P. Linear pattern matching algorlthms. Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1-11. 10.1109/SWAT.1973.13 / Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory by WEINER P. (1973)

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:26 a.m.)
Deposited	2 months, 2 weeks ago (June 17, 2025, 9:39 p.m.)
Indexed	1 week, 4 days ago (Aug. 26, 2025, 2:57 a.m.)
Issued	49 years, 5 months ago (April 1, 1976)
Published	49 years, 5 months ago (April 1, 1976)
Published Online	49 years, 5 months ago (April 1, 1976)
Published Print	49 years, 5 months ago (April 1, 1976)

Funders 0

None

BibTeX

@article{McCreight_1976, title={A Space-Economical Suffix Tree Construction Algorithm}, volume={23}, ISSN={1557-735X}, url={http://dx.doi.org/10.1145/321941.321946}, DOI={10.1145/321941.321946}, number={2}, journal={Journal of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={McCreight, Edward M.}, year={1976}, month=apr, pages={262–272} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        26
      ]
    ],
    "date-time": "2025-08-26T06:57:44Z",
    "timestamp": 1756191464639,
    "version": "3.41.0"
  },
  "reference-count": 8,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "2",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1976,
            4,
            1
          ]
        ],
        "date-time": "1976-04-01T00:00:00Z",
        "timestamp": 197164800000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1976,
        4
      ]
    ]
  },
  "abstract": "<jats:p>A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.</jats:p>",
  "DOI": "10.1145/321941.321946",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:26:10Z",
    "timestamp": 1027769170000
  },
  "page": "262-272",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 1011,
  "title": "A Space-Economical Suffix Tree Construction Algorithm",
  "prefix": "10.1145",
  "volume": "23",
  "author": [
    {
      "given": "Edward M.",
      "family": "McCreight",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1976,
        4
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_2",
      "first-page": "317",
      "volume-title": "The Design and Analysis of Computer Agorithms",
      "author": "AHO A V",
      "year": "1974",
      "unstructured": "AHO , A V ., HoPcaoPr, J.E., AND ULLMAN , J.D. The Design and Analysis of Computer Agorithms . Addison-Wesley , Reading, Mass ., 1974 , Ch 9, pp. 317 - 361 . AHO, A V., HoPcaoPr, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Agorithms. Addison-Wesley, Reading, Mass., 1974, Ch 9, pp. 317-361."
    },
    {
      "key": "e_1_2_1_2_2",
      "volume-title": "Pa.",
      "author": "KIMBALL R B",
      "year": "1974",
      "unstructured": "KIMBALL , R B . A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh , Pa. , April 1974 . KIMBALL, R B. A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh, Pa., April 1974."
    },
    {
      "issue": "3",
      "key": "e_1_2_1_3_2",
      "first-page": "490",
      "volume": "6",
      "author": "KNUTH D.E.",
      "year": "1973",
      "unstructured": "KNUTH , D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass , 1973 , Ch. 6 . 3 , pp. 490 - 493 . KNUTH, D.E. The Art of Computer Programmzng, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass, 1973, Ch. 6.3, pp. 490-493.",
      "journal-title": "Ch."
    },
    {
      "key": "e_1_2_1_4_2",
      "volume-title": "Trondheim",
      "author": "KSUTH D.E",
      "year": "1973",
      "unstructured": "KSUTH , D.E Pattern matching in strings. Unpub. lecture notes , Trondheim , Norway , May 1973 . KSUTH, D.E Pattern matching in strings. Unpub. lecture notes, Trondheim, Norway, May 1973."
    },
    {
      "key": "e_1_2_1_5_2",
      "volume-title": "Calif.",
      "author": "KNUTH D.E.",
      "year": "1974",
      "unstructured": "KNUTH , D.E. , MORRIS , J.H. JR ., AND PRATT , V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford , Calif. , Aug. 1974 . KNUTH, D.E., MORRIS, J.H. JR., AND PRATT, V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford, Calif., Aug. 1974."
    },
    {
      "key": "e_1_2_1_6_2",
      "volume-title": "Applications of the Weiner repetition finder. Unpub. paper",
      "author": "PRATT V R",
      "year": "1973",
      "unstructured": "PRATT , V R . Applications of the Weiner repetition finder. Unpub. paper , Cambridge , Mass ., May 1973 ; rev Oct. 1973 PRATT, V R. Applications of the Weiner repetition finder. Unpub. paper, Cambridge, Mass., May 1973; rev Oct. 1973"
    },
    {
      "key": "e_1_2_1_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/360980.360995"
    },
    {
      "key": "e_1_2_1_8_2",
      "first-page": "1",
      "volume-title": "Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory",
      "author": "WEINER P.",
      "year": "1973",
      "unstructured": "WEINER , P. Linear pattern matching algorlthms . Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory , pp. 1 - 11 . 10.1109/SWAT. 1973 .13 WEINER, P. Linear pattern matching algorlthms. Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1-11. 10.1109/SWAT.1973.13"
    }
  ],
  "container-title": "Journal of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/321941.321946",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/321941.321946",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T01:39:16Z",
    "timestamp": 1750210756000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/321941.321946"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1976,
        4
      ]
    ]
  },
  "references-count": 8,
  "journal-issue": {
    "issue": "2",
    "published-print": {
      "date-parts": [
        [
          1976,
          4
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/321941.321946"
  ],
  "URL": "http://dx.doi.org/10.1145/321941.321946",
  "relation": {},
  "ISSN": [
    "0004-5411",
    "1557-735X"
  ],
  "subject": [],
  "container-title-short": "J. ACM",
  "published": {
    "date-parts": [
      [
        1976,
        4
      ]
    ]
  },
  "assertion": [
    {
      "value": "1976-04-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}