DOI: 10.1145/359842.359859. A fast string searching algorithm

10.1145/359842.359859

Crossref journal-article

Association for Computing Machinery (ACM)

Communications of the ACM (320)

Abstract

An algorithm is presented that searches for the location, “ i l” of the first occurrence of a character string, “ pat ,” in another string, “ string .” During the search operation, the characters of pat are matched starting with the last character of pat . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first i characters of string are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of pat . For a random English pattern of length 5, the algorithm will typically inspect i /4 characters of string before finding a match at i . Furthermore, the algorithm has been implemented so that (on the average) fewer than i + patlen machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in i + patlen , assuming the availability of array space for tables linear in patlen plus the size of the alphabet.

Bibliography

Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762â772.

Authors 2

Robert S. Boyer (first)
J. Strother Moore (additional)

References 5 Referenced 1,523

10.1145/360825.360855
{'volume-title': 'Mass.', 'year': '1972', 'author': 'Beeler M.', 'key': 'e_1_2_1_2_2'} / Mass. by Beeler M. (1972)
{'key': 'e_1_2_1_3_2', 'first-page': '185', 'author': 'Dewey G.', 'year': '1923', 'journal-title': 'Mass.'} / Mass. by Dewey G. (1923)
{'volume-title': 'Calif.', 'year': '1974', 'author': 'Knuth D.E.', 'key': 'e_1_2_1_4_2'} / Calif. by Knuth D.E. (1974)
Knuth D.E. Morris J.H. and Pratt V.R. Fast pattern matching in strings. (to appear in SIAM J. Comput.). Knuth D.E. Morris J.H. and Pratt V.R. Fast pattern matching in strings. (to appear in SIAM J. Comput.).

Dates

Type	When
Created	23 years, 1 month ago (July 27, 2002, 7:34 a.m.)
Deposited	2 months, 2 weeks ago (June 17, 2025, 12:38 p.m.)
Indexed	1 month ago (July 30, 2025, 11:10 a.m.)
Issued	47 years, 11 months ago (Oct. 1, 1977)
Published	47 years, 11 months ago (Oct. 1, 1977)
Published Online	47 years, 11 months ago (Oct. 1, 1977)
Published Print	47 years, 11 months ago (Oct. 1, 1977)

Funders 0

None

BibTeX

@article{Boyer_1977, title={A fast string searching algorithm}, volume={20}, ISSN={1557-7317}, url={http://dx.doi.org/10.1145/359842.359859}, DOI={10.1145/359842.359859}, number={10}, journal={Communications of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Boyer, Robert S. and Moore, J. Strother}, year={1977}, month=oct, pages={762–772} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        30
      ]
    ],
    "date-time": "2025-07-30T15:10:45Z",
    "timestamp": 1753888245438,
    "version": "3.41.0"
  },
  "reference-count": 5,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "10",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1977,
            10,
            1
          ]
        ],
        "date-time": "1977-10-01T00:00:00Z",
        "timestamp": 244512000000
      },
      "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": [
      [
        1977,
        10
      ]
    ]
  },
  "abstract": "<jats:p>\n            An algorithm is presented that searches for the location, \u201c\n            <jats:italic>i</jats:italic>\n            l\u201d of the first occurrence of a character string, \u201c\n            <jats:italic>pat</jats:italic>\n            ,\u201d in another string, \u201c\n            <jats:italic>string</jats:italic>\n            .\u201d During the search operation, the characters of\n            <jats:italic>pat</jats:italic>\n            are matched starting with the last character of\n            <jats:italic>pat</jats:italic>\n            . The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the first\n            <jats:italic>i</jats:italic>\n            characters of\n            <jats:italic>string</jats:italic>\n            are inspected. The number of characters actually inspected (on the average) decreases as a function of the length of\n            <jats:italic>pat</jats:italic>\n            . For a random English pattern of length 5, the algorithm will typically inspect\n            <jats:italic>i</jats:italic>\n            /4 characters of\n            <jats:italic>string</jats:italic>\n            before finding a match at\n            <jats:italic>i</jats:italic>\n            . Furthermore, the algorithm has been implemented so that (on the average) fewer than\n            <jats:italic>i</jats:italic>\n            +\n            <jats:italic>patlen</jats:italic>\n            machine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear in\n            <jats:italic>i</jats:italic>\n            +\n            <jats:italic>patlen</jats:italic>\n            , assuming the availability of array space for tables linear in\n            <jats:italic>patlen</jats:italic>\n            plus the size of the alphabet.\n          </jats:p>",
  "DOI": "10.1145/359842.359859",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:34:59Z",
    "timestamp": 1027769699000
  },
  "page": "762-772",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 1523,
  "title": "A fast string searching algorithm",
  "prefix": "10.1145",
  "volume": "20",
  "author": [
    {
      "given": "Robert S.",
      "family": "Boyer",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Stanford Research Institute, Menlo Park, CA"
        }
      ]
    },
    {
      "given": "J. Strother",
      "family": "Moore",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Xerox Palo Alto Research Center, Palo Alto, CA"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1977,
        10
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/360825.360855"
    },
    {
      "volume-title": "Mass.",
      "year": "1972",
      "author": "Beeler M.",
      "key": "e_1_2_1_2_2"
    },
    {
      "key": "e_1_2_1_3_2",
      "first-page": "185",
      "author": "Dewey G.",
      "year": "1923",
      "journal-title": "Mass."
    },
    {
      "volume-title": "Calif.",
      "year": "1974",
      "author": "Knuth D.E.",
      "key": "e_1_2_1_4_2"
    },
    {
      "key": "e_1_2_1_5_2",
      "unstructured": "Knuth D.E. Morris J.H. and Pratt V.R. Fast pattern matching in strings. (to appear in SIAM J. Comput.).  Knuth D.E. Morris J.H. and Pratt V.R. Fast pattern matching in strings. (to appear in SIAM J. Comput.)."
    }
  ],
  "container-title": "Communications of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/359842.359859",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/359842.359859",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        17
      ]
    ],
    "date-time": "2025-06-17T16:38:00Z",
    "timestamp": 1750178280000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/359842.359859"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1977,
        10
      ]
    ]
  },
  "references-count": 5,
  "journal-issue": {
    "issue": "10",
    "published-print": {
      "date-parts": [
        [
          1977,
          10
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/359842.359859"
  ],
  "URL": "http://dx.doi.org/10.1145/359842.359859",
  "relation": {},
  "ISSN": [
    "0001-0782",
    "1557-7317"
  ],
  "subject": [],
  "container-title-short": "Commun. ACM",
  "published": {
    "date-parts": [
      [
        1977,
        10
      ]
    ]
  },
  "assertion": [
    {
      "value": "1977-10-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}