🔰String pattern matching

Given a main string S of length n and a pattern string T of length m, the process of finding T in S is called pattern matching.If the match is successful, the starting index of the first occurrence of T in S is returned; if the match fails, -1 is returned.

The code in this article uses JavaScript strings, the subscript starts from 0, and the length is obtained by .length.The starting position pos defaults to 0 and must be an integer between 0 and S.length, otherwise a RangeError will be thrown; an empty pattern string returns pos.Example assumes that S and T are both strings.

Characteristics of pattern matching problems:

1. The execution time of the algorithm cannot be ignored: the scale of the problem is usually very large, and it is often necessary to match a large amount of information. 2. The cumulative benefits gained from algorithm improvements cannot be ignored: pattern matching operations are often called and executed with high frequency.

🔸 Two matching methods are introduced:

1️⃣: BF algorithm
2️⃣: KMP algorithm

1️⃣Pattern matching—BF algorithm

Basic idea🖌️:

📝 Compare starting from the starting position of the main string pos with the first character of the pattern string T.If they are equal, the subsequent characters of the two will continue to be compared; if there is a mismatch, the next position from the starting point of this match will be compared with the first character of T again.Repeat the above process until all characters in T are matched successfully;

If the main string has been scanned but all pattern strings have not been matched, it means that the matching has failed.

Algorithm process🖌️:

STEP1: Set the main string subscript i = pos, and the pattern string subscript j = 0;

STEP2: Loop until all characters of S or T are compared;

2.1 If S[i] === T[j], then i and j are increased by 1 at the same time;
2.2 Otherwise, let i = i - j + 1, j = 0 and prepare for the next comparison.

STEP3: If j === T.length, the match is successful and i - T.length is returned; otherwise the match fails and -1 is returned.

Algorithm steps🖌️:

Entry function (main string, pattern string, starting position)

1. There are two variables, one is the main string subscript i, and the other is the pattern string subscript j.
2. Compare two strings: if they are the same, move the subscript backward; otherwise, return to the starting point of the next match.

Algorithm description🖌️:

// S 为主串，T 为模式串，pos 为主串的起始下标
function Index_BF(S, T, pos = 0) {
    if (!Number.isInteger(pos) || pos < 0 || pos > S.length) {
        throw new RangeError('pos 必须是 0 到 S.length 之间的整数');
    }
    let i = pos, j = 0;
    const sl = S.length, tl = T.length;
    while (i < sl && j < tl) {
        if (S[i] === T[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j === tl) {
        return i - tl;
    } else {
        return -1;
    }
}
console.log(Index_BF('abdefd', 'ab')); // 0
console.log(Index_BF('ab', 'b')); // 1
console.log(Index_BF('xb', 'ab')); // -1
console.log(Index_BF('ac', 'ab')); // -1
console.log(Index_BF('abc', '', 2)); // 2

Algorithm performance🖌️:

Assume that the length of the main string S is n and the length of the non-empty pattern string T is m. Start searching from pos = 0. Consider two typical situations:

👉case1️⃣: Each unsuccessful match is a mismatch at the first character of T.

If the match is finally successful at subscript r, the first r passes will be compared once each, and the successful one will be compared m times, for a total of r + m times.In this case, the time complexity is O(n + m); if the first pass matches successfully, it only needs to be compared m times, and the best time complexity is O(m).

👉case2️⃣: Each unsuccessful match has a mismatch at the last character of T.

If the match is finally successful at subscript r, the first r passes will be compared m times each, plus the successful one, for a total of (r + 1) * m times.The worst time complexity is O(nm).For example, if both the main string and the pattern string contain a large number of consecutive as, but the pattern string ends with b, it is possible to repeat the comparison of already checked characters.

Extra space complexity: O(1).The empty pattern string returns pos directly, which takes O(1).

2️⃣Pattern matching—KMP algorithm

KMP algorithm idea🖌️

This algorithm is an improvement on the BF algorithm.When a mismatch occurs in each match, the main string pointer i is not traced back, but the pattern string is moved using the suffix relationship of the matched part and the comparison is continued.

next[j] in the code of this article represents the length of the longest equal true prefix and true suffix of the pattern string prefix T[0..j]."True" means not including the entire prefix itself.For example, the longest equal true prefix and true suffix of ababa is aba, with length 3.

1. Summary 1️⃣ : next [ j ] meaning

   When S[i] and T[j] mismatch and j > 0, T[0..j-1] has been matched, and j = next[j - 1] can be set to retain the reusable suffixes and suffixes in this part of characters, and then compare the current S[i].At the same mismatch position, the larger the reserved length, the smaller the distance the pattern string moves; the advantage of KMP is to avoid repeated scanning of the main string, and the overall efficiency cannot be judged based only on the size of the next value.

2. Summary 2️⃣ : Fallback mode string pointer

   First, i in the main string does not go back, and j in the pattern string goes back according to the next array, which is only related to the pattern string T.

   Second, if there is still a mismatch after rolling back, continue to set j = next[j - 1]; if there is still a mismatch when j === 0, add 1 to i and compare the next character of the main string.

3. Method to calculate next array

   🔖Case 1: There is no non-empty equal true prefix and true suffix for a single character, so next[0] = 0; the next array of an empty pattern string is empty.

   🔖Case 2: When calculating next[i], start from j = next[i - 1].If T[i] === T[j], the original equal suffixes can be extended by one character at the same time, let next[i] = j + 1.

   🔖Case 3: If there is a mismatch and j > 0, let j = next[j - 1] and try a shorter equal suffix; if there is still a mismatch when j === 0, then next[i] = 0.

KMP algorithm description🖌️

function index_KMP(S, T, pos = 0) {
    if (!Number.isInteger(pos) || pos < 0 || pos > S.length) {
        throw new RangeError('pos 必须是 0 到 S.length 之间的整数');
    }
    const next = get_next(T);
    const sl = S.length, tl = T.length;
    let i = pos, j = 0;
    while (i < sl && j < tl) {
        if (S[i] === T[j]) {
            i++;
            j++;
        } else if (j === 0) {
            i++;
        } else {
            j = next[j - 1]; // 只回退模式串指针，保留当前主串字符
        }
    }
    return j === tl ? i - tl : -1;
}

// 返回最长相等真前缀与真后缀的长度数组
function get_next(T) {
    const next = new Array(T.length).fill(0);
    let i = 1, j = 0;
    while (i < T.length) {
        if (T[i] === T[j]) {
            j++;
            next[i] = j;
            i++;
        } else if (j === 0) {
            next[i] = 0;
            i++;
        } else {
            j = next[j - 1]; // 回退到更短的相等前后缀
        }
    }
    return next;
}

console.log(index_KMP('acabaabaabcacaabc', 'abaabcac')); // 5
console.log(index_KMP('xxaab', 'aab')); // 2
console.log(index_KMP('aaabaaaab', 'aaaab')); // 4
console.log(index_KMP('xxx', 'ab')); // -1
console.log(index_KMP('abc', '', 2)); // 2

KMP algorithm exercise🖌️:

Assume the main string S = "aaabaaaab", the pattern string T = "aaaab", the length of S = 9, and the length of T m = 5.According to the 0-based subscript in the code, the prefix length array of T is as follows:

j	0	1	2	3	4
T[j]	a	a	a	a	b
next[j]	0	1	2	3	0

When i = 3, j = 3, S[3] = 'b' does not match T[3] = 'a'.j returns to 2, 1, and 0 sequentially according to next[j - 1], still mismatching, and then i advances to 4.After continuing the comparison, S[4..8] matches T successfully, and the function returns the subscript 4.

nextVal optimization: In the above rollback process, the first four characters of T are all a. It is known that the current main string character b is not equal to one of the a, so the repeated comparison of the remaining same characters can be skipped.nextVal exploits this to further optimize fallback.

To illustrate the derivation of nextVal in the textbook, the following table uses 1 base subscript, and uses nextPos[j] to represent the character position to fall back to after mismatch: nextPos[1] = 0; when j > 1, it is equal to the longest equal true suffix length of the matched part T[1..j-1] plus 1.The fallback position 0 means skipping the current main string characters and restarting the comparison from the first character of the pattern string.Running the example still uses the 0-based prefix length array from above.

j	1	2	3	4	5
T[j]	a	a	a	a	b
nextPos[j]	0	1	2	3	4
nextVal[j]	0	0	0	0	4

Summary: Let k = nextPos[j].If k === 0, then nextVal[j] = 0; if k > 0 and T[j] and T[k] are not equal, then nextVal[j] = k; if they are equal, then nextVal[j] = nextVal[k], skipping the same-character comparison that is destined to mismatch.

Time complexity of KMP algorithm🖌️

Assume that the length of the main string S is n and the length of the pattern string T is m. It takes O(m) time to construct the next array.i does not fall back when matching; j only increases when matching is successful, and the fallback will decrease every time there is a mismatch, so the cumulative number of rollbacks does not exceed the cumulative number of increases.Even if the same main string character participates in multiple comparisons, the total time of scanning is still O(n), and the total time complexity is O(n + m).

Extra space complexity: O(m), used to save the next array of pattern strings.