Skip to content

3455. Shortest Matching Substring 👍

  • Time: $O(|\texttt{s}| + |\texttt{p}|)$
  • Space: $O(|\texttt{s}| + |\texttt{p}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
 public:
  int shortestMatchingSubstring(string s, string p) {
    const auto [a, b, c] = split(p);
    const int ns = s.length();
    const int na = a.length();
    const int nb = b.length();
    const int nc = c.length();
    const vector<int> lpsA = getLPS(a + '#' + s);
    const vector<int> lpsB = getLPS(b + '#' + s);
    const vector<int> lpsC = getLPS(c + '#' + s);
    int ans = INT_MAX;

    for (int i = 0, j = 0, k = 0; i + nb + nc < ns; ++i) {
      while (i < ns && lpsA[na + 1 + i] != na)
        ++i;
      while (j < ns && (j < i + nb || lpsB[nb + 1 + j] != nb))
        ++j;
      while (k < ns && (k < j + nc || lpsC[nc + 1 + k] != nc))
        ++k;
      if (k == ns)
        break;
      ans = min(ans, k - i + na);
    }

    return ans == INT_MAX ? -1 : ans;
  }

 private:
  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  vector<int> getLPS(const string& pattern) {
    vector<int> lps(pattern.length());
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern[j] != pattern[i])
        j = lps[j - 1];
      if (pattern[i] == pattern[j])
        lps[i] = ++j;
    }
    return lps;
  }

  tuple<string, string, string> split(const string& p) {
    const int i = p.find('*');
    const int j = p.find('*', i + 1);
    return {p.substr(0, i), p.substr(i + 1, j - i - 1), p.substr(j + 1)};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
  public int shortestMatchingSubstring(String s, String p) {
    final String[] parts = split(p);
    final String a = parts[0];
    final String b = parts[1];
    final String c = parts[2];
    final int ns = s.length();
    final int na = a.length();
    final int nb = b.length();
    final int nc = c.length();
    int[] lpsA = getLPS(a + "#" + s);
    int[] lpsB = getLPS(b + "#" + s);
    int[] lpsC = getLPS(c + "#" + s);
    int ans = Integer.MAX_VALUE;

    for (int i = 0, j = 0, k = 0; i + nb + nc < ns; ++i) {
      while (i < ns && lpsA[na + 1 + i] != na)
        ++i;
      while (j < ns && (j < i + nb || lpsB[nb + 1 + j] != nb))
        ++j;
      while (k < ns && (k < j + nc || lpsC[nc + 1 + k] != nc))
        ++k;
      if (k == ns)
        break;
      ans = Math.min(ans, k - i + na);
    }

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }

  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  private int[] getLPS(String pattern) {
    int[] lps = new int[pattern.length()];
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
        j = lps[j - 1];
      if (pattern.charAt(i) == pattern.charAt(j))
        lps[i] = ++j;
    }
    return lps;
  }

  private String[] split(final String p) {
    final int i = p.indexOf('*');
    final int j = p.indexOf('*', i + 1);
    return new String[] {p.substring(0, i), p.substring(i + 1, j), p.substring(j + 1)};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
  def shortestMatchingSubstring(self, s: str, p: str) -> int:
    n = len(s)
    a, b, c = p.split('*')
    lpsA = self._getLPS(a + '#' + s)[len(a) + 1:]
    lpsB = self._getLPS(b + '#' + s)[len(b) + 1:]
    lpsC = self._getLPS(c + '#' + s)[len(c) + 1:]
    ans = math.inf

    i = 0  # lpsA's index
    j = 0  # lpsB's index
    k = 0  # lpsC's index
    while i + len(b) + len(c) < n:
      while i < n and lpsA[i] != len(a):
        i += 1
      while j < n and (j < i + len(b) or lpsB[j] != len(b)):
        j += 1
      while k < n and (k < j + len(c) or lpsC[k] != len(c)):
        k += 1
      if k == n:
        break
      ans = min(ans, k - i + len(a))
      i += 1

    return -1 if ans == math.inf else ans

  def _getLPS(self, pattern: str) -> list[int]:
    """
    Returns the lps array, where lps[i] is the length of the longest prefix of
    pattern[0..i] which is also a suffix of this substring.
    """
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
      while j > 0 and pattern[j] != pattern[i]:
        j = lps[j - 1]
      if pattern[i] == pattern[j]:
        lps[i] = j + 1
        j += 1
    return lps