AIOJ

This page briefly introduces the string matching problem and its solutions.

String matching problem

Definition

Also called pattern matching. The problem can be summarized as “given strings $S$ and $T$ , find in text string $S$ the substring $T$ ”. The string $T$ is called the pattern string (pattern).

Types

Single-pattern matching: given a pattern string and a string to be matched, find all positions of the former in the latter.
Multiple-pattern matching: given multiple pattern strings and a string to be matched, find all positions of these pattern strings in the latter.
- If there are multiple strings to be matched, concatenate them directly and process the result as one string to be matched.
- This can be treated directly as single-pattern matching, but the efficiency is not high enough.
Other types: for example, matching any suffix of a string, matching any suffix of multiple strings, and so on …

Brute-force approach

The algorithm is abbreviated as BF (Brute Force). Its basic idea is to start by comparing the first character of the text string $S$ with the first character of the pattern string $T$ . If they are equal, continue comparing their subsequent characters; otherwise, return the pattern string $T$ to its first character and compare it with the second character of the text string $S$ again. Repeat this until all characters in $S$ or $T$ have been compared.

Implementation

C++

/*
 * s: the text string to be matched
 * t: the pattern string
 * n: the length of the text string
 * m: the 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;
}

Python

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 text string and $m$ the length of the pattern string. By default, $m\ll n$ .

When the BF algorithm succeeds, in the best case there is only one successful pass. This pass makes $m$ comparisons, while every other unsuccessful pass fails on the first character of the pattern and requires $n-m$ more comparisons, for a total of $n$ comparisons; hence the time complexity is $O(n)$ . In the worst case, the number of successful passes is $n-m+1$ , each pass makes $m$ comparisons, and the total number of comparisons is $m(n-m+1)$ ; hence the time complexity is $O(mn)$ .

When the BF algorithm fails, in the best case every unsuccessful pass fails on the first character of the pattern. The BF algorithm performs $n-m+1$ comparisons, so the time complexity is $O(n)$ . In the worst case, every unsuccessful pass fails on the last character of the pattern. The BF algorithm performs $m(n-m+1)$ comparisons, so the time complexity is $O(mn)$ .

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

Hashing approach

See: String hashing

KMP algorithm

See: Prefix function and KMP algorithm