{
  "id": "enwiki-001372977915",
  "slug": "two-way-string-matching-algorithm",
  "title": "Two-way string-matching algorithm",
  "qid": "",
  "lead": "In computer science, the two-way string-matching algorithm (or Crochemore-Perrin string-matching algorithm) is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. It searches for copies of a \"needle\" of length m in a \"haystack\" of length n. After preprocessing the needle in time O(m), the actual search takes time O(n) linear in the length of the haystack. The two-way algorithm can be viewed as a combination of the forward-going Knuth–Morris–Pratt algorithm (KMP) and the backward-running Boyer–Moore string-search algorithm (BM). Like those two, the two-way algorithm preprocesses the needle to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered. Unlike BM and KMP, it uses only O(1) additional space to store information about those partial repeats (assuming the transdichotomous model, where an index of ⌈log 2 (m)⌉ bits is counted as a single word). The preprocessing computes the \"period\" of the needle, the minimum offset between two consecutive matches (a value between 1 and m), and a \"critical factorization\" of the needle into a prefix and suffix with particular properties, specified by the length of the prefix (also less than m). The actual matching operation performs at most 2n − m comparisons.…",
  "body": "In computer science, the two-way string-matching algorithm (or Crochemore-Perrin string-matching algorithm) is a string-searching algorithm, discovered by Maxime Crochemore and Dominique Perrin in 1991. It searches for copies of a \"needle\" of length m in a \"haystack\" of length n. After preprocessing the needle in time O(m), the actual search takes time O(n) linear in the length of the haystack. The two-way algorithm can be viewed as a combination of the forward-going Knuth–Morris–Pratt algorithm (KMP) and the backward-running Boyer–Moore string-search algorithm (BM). Like those two, the two-way algorithm preprocesses the needle to find partially repeating periods and computes “shifts” based on them, indicating what offset to “jump” to in the haystack when a given character is encountered. Unlike BM and KMP, it uses only O(1) additional space to store information about those partial repeats (assuming the transdichotomous model, where an index of ⌈log 2 (m)⌉ bits is counted as a single word). The preprocessing computes the \"period\" of the needle, the minimum offset between two consecutive matches (a value between 1 and m), and a \"critical factorization\" of the needle into a prefix and suffix with particular properties, specified by the length of the prefix (also less than m). The actual matching operation performs at most 2n − m comparisons. Breslauer later published two improved variants performing fewer comparisons, at the cost of storing additional data about the preprocessed needle: The first one performs at most n + ⌊(n − m)/2⌋ comparisons, ⌈(n − m)/2⌉ fewer than the original. It must however store ⌈log φ m⌉ additional offsets into the needle. The second adapts it to only store a constant number of such offsets, denoted c, but must perform n + ⌊( + ε)(n − m)⌋ comparisons, with ε = (F c+2 − 1) −1 ∈ O(φ −c ) going to zero exponentially quickly as c increases. The algorithm is considered fairly efficient in practice, being cache-friendly and using several operations that can be implemented in well-optimized subroutines. It is used by the C standard libraries glibc, newlib, and musl, to implement the memmem and strstr family of substring functions. As with most advanced string-search algorithms, the naïve implementation may be more efficient on small-enough instances; this is especially so if the needle isn't searched in multiple haystacks, which would amortize the preprocessing cost. if a = b return 0 if a idx2 return [idx1, per1] else return [idx2, per2] The comparison proceeds by first matching for the right-hand-side, and then for the left-hand-side if it matches. Linear-time skipping is done using the period. function match(needle, haystack) needle_len ← len(needle) haystack_len ← len(haystack) [length, cur_period] ← crit_fact(needle) Matches ← {} set of matches. Match the suffix. Use a library function like memcmp, or write your own loop. if needle[0] ... needle[length] == needle[length + 1] ... needle[length + cur_period] Matches ← {} pos ← 0 s ← 0 TODO. At least put the skip in.",
  "categories": [
    "23228400",
    "23603337",
    "26220375",
    "30181014"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1372977915",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1788416575.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001372977915",
    "type": "webpage",
    "title": "Two-way string-matching algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/two-way-string-matching-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          13
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          13
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001372977915",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1372977915",
    "note": "Immutable snapshot enwiki-001372977915"
  }
}