class Solution {
public:
int shortestMatchingSubstring(string s, string p) {
}
};
3455. 最短匹配子字符串
给你一个字符串 s 和一个模式字符串 p，其中 p 恰好 包含 两个 '*' 字符。
p 中的 '*' 匹配零个或多个字符的任何序列。
返回 s 中与 p 匹配的 最短 子字符串的长度。如果没有这样的子字符串，返回 -1。
子字符串 是字符串中的一个连续字符序列（空子字符串也被认为是合法字符串）。
示例 1：
输入： s = "abaacbaecebce", p = "ba*c*ce"
输出： 8
解释：
在 s 中，p 的最短匹配子字符串是 "baecebce"。
示例 2：
输入： s = "baccbaadbc", p = "cc*baa*adb"
输出： -1
解释：
在 s 中没有匹配的子字符串。
示例 3：
输入： s = "a", p = "**"
输出： 0
解释：
空子字符串是最短的匹配子字符串。
示例 4：
输入： s = "madlogic", p = "*adlogi*"
输出： 6
解释：
在 s 中，p 的最短匹配子字符串是 "adlogi"。
提示：
1 <= s.length <= 1052 <= p.length <= 105s 仅包含小写英文字母。p 仅包含小写英文字母，并且恰好包含两个 '*'。原站题解
python3 解法, 执行用时: 1345 ms, 内存消耗: 29.4 MB, 提交时间: 2025-02-24 12:49:27
# kmp + 枚举中间 + 三指针
class Solution:
def shortestMatchingSubstring(self, s: str, p: str) -> int:
p1, p2, p3 = p.split('*')
# 三段各自在 s 中的所有匹配位置
pos1 = self.kmp_search(s, p1)
pos2 = self.kmp_search(s, p2)
pos3 = self.kmp_search(s, p3)
ans = inf
i = k = 0
# 枚举中间（第二段），维护最近的左右（第一段和第三段）
for j in pos2:
# 右边找离 j 最近的子串（但不能重叠）
while k < len(pos3) and pos3[k] < j + len(p2):
k += 1
if k == len(pos3): # 右边没有
break
# 左边找离 j 最近的子串（但不能重叠）
while i < len(pos1) and pos1[i] <= j - len(p1):
i += 1
# 循环结束后，pos1[i-1] 是左边离 j 最近的子串下标（首字母在 s 中的下标）
if i > 0:
ans = min(ans, pos3[k] + len(p3) - pos1[i - 1])
return -1 if ans == inf else ans
# 计算字符串 p 的 pi 数组
def calc_pi(self, p: str) -> List[int]:
pi = [0] * len(p)
cnt = 0
for i in range(1, len(p)):
v = p[i]
while cnt > 0 and p[cnt] != v:
cnt = pi[cnt - 1]
if p[cnt] == v:
cnt += 1
pi[i] = cnt
return pi
# 在文本串 s 中查找模式串 p，返回所有成功匹配的位置（p[0] 在 s 中的下标）
def kmp_search(self, s: str, p: str) -> List[int]:
if not p:
# s 的所有位置都能匹配空串，包括 len(s)
return list(range(len(s) + 1))
pi = self.calc_pi(p)
pos = []
cnt = 0
for i, v in enumerate(s):
while cnt > 0 and p[cnt] != v:
cnt = pi[cnt - 1]
if p[cnt] == v:
cnt += 1
if cnt == len(p):
pos.append(i - len(p) + 1)
cnt = pi[cnt - 1]
return pos
golang 解法, 执行用时: 47 ms, 内存消耗: 10.2 MB, 提交时间: 2025-02-24 12:48:51
// 计算字符串 p 的 pi 数组
func calcPi(p string) []int {
pi := make([]int, len(p))
match := 0
for i := 1; i < len(pi); i++ {
v := p[i]
for match > 0 && p[match] != v {
match = pi[match-1]
}
if p[match] == v {
match++
}
pi[i] = match
}
return pi
}
// 在文本串 s 中查找模式串 p，返回所有成功匹配的位置（p[0] 在 s 中的下标）
func kmpSearch(s, p string) (pos []int) {
if p == "" {
// s 的所有位置都能匹配空串，包括 len(s)
pos = make([]int, len(s)+1)
for i := range pos {
pos[i] = i
}
return
}
pi := calcPi(p)
match := 0
for i := range s {
v := s[i]
for match > 0 && p[match] != v {
match = pi[match-1]
}
if p[match] == v {
match++
}
if match == len(p) {
pos = append(pos, i-len(p)+1)
match = pi[match-1]
}
}
return
}
func shortestMatchingSubstring(s, p string) int {
sp := strings.Split(p, "*")
p1, p2, p3 := sp[0], sp[1], sp[2]
// 三段各自在 s 中的所有匹配位置
pos1 := kmpSearch(s, p1)
pos2 := kmpSearch(s, p2)
pos3 := kmpSearch(s, p3)
ans := math.MaxInt
i, k := 0, 0
// 枚举中间（第二段），维护最近的左右（第一段和第三段）
for _, j := range pos2 {
// 右边找离 j 最近的子串（但不能重叠）
for k < len(pos3) && pos3[k] < j+len(p2) {
k++
}
if k == len(pos3) { // 右边没有
break
}
// 左边找离 j 最近的子串（但不能重叠）
for i < len(pos1) && pos1[i] <= j-len(p1) {
i++
}
// 循环结束后，posL[i-1] 是左边离 j 最近的子串下标（首字母在 s 中的下标）
if i > 0 {
ans = min(ans, pos3[k]+len(p3)-pos1[i-1])
}
}
if ans == math.MaxInt {
return -1
}
return ans
}
java 解法, 执行用时: 86 ms, 内存消耗: 54.5 MB, 提交时间: 2025-02-24 12:48:27
class Solution {
public int shortestMatchingSubstring(String S, String p) {
char[] s = S.toCharArray();
String[] sp = p.split("\\*", -1);
char[] p1 = sp[0].toCharArray();
char[] p2 = sp[1].toCharArray();
char[] p3 = sp[2].toCharArray();
// 三段各自在 s 中的所有匹配位置
List<Integer> pos1 = kmpSearch(s, p1);
List<Integer> pos2 = kmpSearch(s, p2);
List<Integer> pos3 = kmpSearch(s, p3);
int ans = Integer.MAX_VALUE;
int i = 0;
int k = 0;
// 枚举中间（第二段），维护最近的左右（第一段和第三段）
for (int j : pos2) {
// 右边找离 j 最近的子串（但不能重叠）
while (k < pos3.size() && pos3.get(k) < j + p2.length) {
k++;
}
if (k == pos3.size()) { // 右边没有
break;
}
// 左边找离 j 最近的子串（但不能重叠）
while (i < pos1.size() && pos1.get(i) <= j - p1.length) {
i++;
}
// 循环结束后，pos1.get(i-1) 是左边离 j 最近的子串下标（首字母在 s 中的下标）
if (i > 0) {
ans = Math.min(ans, pos3.get(k) + p3.length - pos1.get(i - 1));
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// 计算字符串 p 的 pi 数组
private int[] calcPi(char[] p) {
int[] pi = new int[p.length];
int match = 0;
for (int i = 1; i < p.length; i++) {
char v = p[i];
while (match > 0 && p[match] != v) {
match = pi[match - 1];
}
if (p[match] == v) {
match++;
}
pi[i] = match;
}
return pi;
}
// 在文本串 s 中查找模式串 p，返回所有成功匹配的位置（p[0] 在 s 中的下标）
private List<Integer> kmpSearch(char[] s, char[] p) {
if (p.length == 0) {
// s 的所有位置都能匹配空串，包括 s.length
List<Integer> pos = new ArrayList<>(s.length + 1);
for (int i = 0; i <= s.length; i++) {
pos.add(i);
}
return pos;
}
int[] pi = calcPi(p);
List<Integer> pos = new ArrayList<>();
int match = 0;
for (int i = 0; i < s.length; i++) {
char v = s[i];
while (match > 0 && p[match] != v) {
match = pi[match - 1];
}
if (p[match] == v) {
match++;
}
if (match == p.length) {
pos.add(i - p.length + 1);
match = pi[match - 1];
}
}
return pos;
}
}
cpp 解法, 执行用时: 86 ms, 内存消耗: 65.4 MB, 提交时间: 2025-02-24 12:48:06
class Solution {
// 计算字符串 p 的 pi 数组
vector<int> calcPi(string& p) {
vector<int> pi(p.size());
int match = 0;
for (int i = 1; i < p.size(); i++) {
char v = p[i];
while (match > 0 && p[match] != v) {
match = pi[match - 1];
}
if (p[match] == v) {
match++;
}
pi[i] = match;
}
return pi;
}
// 在文本串 s 中查找模式串 p，返回所有成功匹配的位置（p[0] 在 s 中的下标）
vector<int> kmp_search(string& s, string p) {
if (p.empty()) {
// s 的所有位置都能匹配空串，包括 s.size()
vector<int> pos(s.size() + 1);
iota(pos.begin(), pos.end(), 0);
return pos;
}
vector<int> pi = calcPi(p);
vector<int> pos;
int match = 0;
for (int i = 0; i < s.size(); i++) {
char v = s[i];
while (match > 0 && p[match] != v) {
match = pi[match - 1];
}
if (p[match] == v) {
match++;
}
if (match == p.size()) {
pos.push_back(i - p.size() + 1);
match = pi[match - 1];
}
}
return pos;
}
public:
int shortestMatchingSubstring(string s, string p) {
int star1 = p.find('*');
int star2 = p.rfind('*');
// 三段各自在 s 中的所有匹配位置
vector<int> pos1 = kmp_search(s, p.substr(0, star1));
vector<int> pos2 = kmp_search(s, p.substr(star1 + 1, star2 - star1 - 1));
vector<int> pos3 = kmp_search(s, p.substr(star2 + 1));
// 每一段的长度
int len1 = star1;
int len2 = star2 - star1 - 1;
int len3 = p.size() - star2 - 1;
int ans = INT_MAX;
int i = 0, k = 0;
// 枚举中间（第二段），维护最近的左右（第一段和第三段）
for (int j : pos2) {
// 右边找离 j 最近的子串（但不能重叠）
while (k < pos3.size() && pos3[k] < j + len2) {
k++;
}
if (k == pos3.size()) { // 右边没有
break;
}
// 左边找离 j 最近的子串（但不能重叠）
while (i < pos1.size() && pos1[i] <= j - len1) {
i++;
}
// 循环结束后，pos1[i-1] 是左边离 j 最近的子串下标（首字母在 s 中的下标）
if (i > 0) {
ans = min(ans, pos3[k] + len3 - pos1[i - 1]);
}
}
return ans == INT_MAX ? -1 : ans;
}
};