Skip to content

String Matching

This page provides a brief introduction to the string matching problem and its solutions.

String Matching Problem

Definition

Also known as pattern matching. This problem can be summarized as "given strings \(S\) and \(T\), find the substring \(T\) in the main string \(S\)". The character string \(T\) is called the pattern string.

Types

  • Single String Matching: Given one pattern string and one text string, find all positions of the pattern in the text.
  • Multiple String Matching: Given multiple pattern strings and one text string, find all positions of these patterns in the text.
    • When there are multiple text strings, they can be concatenated into a single text string for processing.
    • It can be treated as single string matching directly, but this is not efficient enough.
  • Other Types: For example, matching any suffix of a string, matching any suffix of multiple strings, etc.

Brute Force Approach

Abbreviated as BF (Brute Force) algorithm. The basic idea of this algorithm is to start comparing the first character of the main string \(S\) with the first character of the pattern string \(T\). If they are equal, continue comparing their subsequent characters; otherwise, the pattern string \(T\) falls back to its first character and is compared again with the second character of the main string \(S\). This process repeats until all characters in \(S\) or \(T\) have been compared.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/*
 * s: main string to be matched
 * t: pattern string
 * n: length of the main string
 * m: length of the pattern string
 */
std::vector<int> match(char *s, char *t, int n, int m) {
  std::vector<int> ans;
  int i, j;
  for (i = 0; i < n - m + 1; i++) {
    for (j = 0; j < m; j++) {
      if (s[i + j] != t[j]) break;
    }
    if (j == m) ans.push_back(i);
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def match(s, t, n, m):
    if m < 1:
        return []

    ans = []
    for i in range(0, n - m + 1):
        for j in range(0, m):
            if s[i + j] != t[j]:
                break
        else:
            ans.append(i)
    return ans

Time Complexity

Let \(n\) be the length of the main string and \(m\) be the length of the pattern string. It is assumed that \(m\ll n\).

When the BF algorithm matches successfully, in the best case, only one successful match occurs, requiring \(m\) comparisons for that match, and each unsuccessful match happens at the first character of the pattern, requiring an additional \(n-m\) comparisons, totaling \(n\) comparisons. Thus, the time complexity is \(O(n)\). In the worst case, the number of successful matches is \(n-m+1\), each requiring \(m\) comparisons, resulting in a total of \(m(n-m+1)\) comparisons, so the time complexity is \(O(mn)\).

When the BF algorithm fails to match, in the best case, each unsuccessful match occurs at the first character of the pattern. The BF algorithm performs \(n-m+1\) comparisons, with a time complexity of \(O(n)\). In the worst case, each unsuccessful match occurs at the last character of the pattern. The BF algorithm performs \(m(n-m+1)\) comparisons, with a time complexity of \(O(mn)\).

If the pattern string has at least two different characters, the average time complexity of the BF algorithm is \(O(n)\). However, in OI problems, the given strings are generally not purely random.

Hash Method

See: String Hashing

KMP Algorithm

See: Prefix Function and KMP Algorithm

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用