practice
LeetCode 334 - Reverse String
LeetCode 541 - Reverse String II
LeetCode 151 - Reverse Words in a String

Notes

  • revert a string twice will stay unchanged, use this trick on some sub-strings can reach some complex transformation.

String Matching (KMP)

Naive Approach

The naive approach to string matching involves comparing the pattern with the text character by character. If a mismatch is found, the pattern is shifted by one position and the comparison is repeated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int naiveSearch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (j == m) {
            return i;
        }
    }
    return -1;
}

This approach has a time complexity of O(n * m) in the worst case, where n is the length of the text and m is the length of the pattern.
The main drawback of this approach is that it does not take advantage of the information in the pattern to avoid unnecessary comparisons.

KMP Algorithm

This works because if the suffix matches, then its identical prefix should also match. Therefore, we can skip comparisons for those letters. This approach eliminates the need to backtrack the pointer for the target string and uses the pointers in the pattern and prepared information to achieve the same result.

Prepare LSP (Longest Proper Prefix which is also a suffix)

  • Step 1: Initialize a LPS array of the same size as the pattern and set all array elements to -1, where -1 denotes no LPS is recognized at the given index.
  • Step 2: Define two indices j = 0, i = 1.
  • Step 3: Compare the letters at pattern[i] and pattern[j]
    • match: 
      1
      2
      3
      LPS[i] = j
      i += 1
      j += 1
    • mismatch:
      1
      2
      3
      4
      5
      if (j == 0) {
          i += 1
      } else {
          j = LPS[j - 1] + 1
      }

      Repeat step 3 until all the elements in the pattern are iterated.

String Matching

The process of String Matching and Building LPS array are quite similiar.

  • Step 1: Define two pointers i, j to denote the current index at the main string and pattern respectively.
  • Step 2: Compare the letters at string[i] and pattern[j]
    • match:
      1
      2
      i += 1
      j += 1
    • mismatch
      1
      2
      3
      4
      5
      if (j == 0) {
          i += 1
      } else {
          j = LPS[j - 1] + 1
      }
      repeat step 2 until the whole pattern is matched or the length of unchecked in the main string is less than the length if the pattern string.

Practice
LeetCode 28 - Find the Index of the First Occurrence in a String
LeetCode 459 - Repeated Substring Pattern

Reference

Knuth-Morris-Pratt(KMP) Algorithm: String Matching