class Solution {
public:
vector<int> beautifulIndices(string s, string a, string b, int k) {
}
};
3008. 找出数组中的美丽下标 II
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：
0 <= i <= s.length - a.lengths[i..(i + a.length - 1)] == aj 使得：
0 <= j <= s.length - b.lengths[j..(j + b.length - 1)] == b|j - i| <= k以数组形式按 从小到大排序 返回美丽下标。
示例 1：
输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15 输出：[16,33] 解释：存在 2 个美丽下标：[16,33]。 - 下标 16 是美丽下标，因为 s[16..17] == "my" ，且存在下标 4 ，满足 s[4..11] == "squirrel" 且 |16 - 4| <= 15 。 - 下标 33 是美丽下标，因为 s[33..34] == "my" ，且存在下标 18 ，满足 s[18..25] == "squirrel" 且 |33 - 18| <= 15 。 因此返回 [16,33] 作为结果。
示例 2：
输入：s = "abcd", a = "a", b = "a", k = 4 输出：[0] 解释：存在 1 个美丽下标：[0]。 - 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。 因此返回 [0] 作为结果。
提示：
1 <= k <= s.length <= 5 * 1051 <= a.length, b.length <= 5 * 105s、a、和 b 只包含小写英文字母。原站题解
golang 解法, 执行用时: 123 ms, 内存消耗: 14.6 MB, 提交时间: 2024-01-22 10:07:15
// 二分
func beautifulIndices(s, a, b string, k int) (ans []int) {
posA := kmp(s, a)
posB := kmp(s, b)
for _, i := range posA {
bi := sort.SearchInts(posB, i)
// 离 i 最近的 j 是 posB[bi] 或 posB[bi-1]
if bi < len(posB) && posB[bi]-i <= k || bi > 0 && i-posB[bi-1] <= k {
ans = append(ans, i)
}
}
return
}
// 双指针
func beautifulIndices2(s, a, b string, k int) (ans []int) {
posA := kmp(s, a)
posB := kmp(s, b)
j, m := 0, len(posB)
for _, i := range posA {
for j < m && posB[j] < i-k {
j++
}
if j < m && posB[j] <= i+k {
ans = append(ans, i)
}
}
return
}
func kmp(text, pattern string) (pos []int) {
m := len(pattern)
pi := make([]int, m)
cnt := 0
for i := 1; i < m; i++ {
v := pattern[i]
for cnt > 0 && pattern[cnt] != v {
cnt = pi[cnt-1]
}
if pattern[cnt] == v {
cnt++
}
pi[i] = cnt
}
cnt = 0
for i, v := range text {
for cnt > 0 && pattern[cnt] != byte(v) {
cnt = pi[cnt-1]
}
if pattern[cnt] == byte(v) {
cnt++
}
if cnt == m {
pos = append(pos, i-m+1)
cnt = pi[cnt-1]
}
}
return
}
java 解法, 执行用时: 48 ms, 内存消耗: 71.7 MB, 提交时间: 2024-01-22 10:06:08
class Solution {
// 二分
public List<Integer> beautifulIndices(String s, String a, String b, int k) {
char[] text = s.toCharArray();
List<Integer> posA = kmp(text, a.toCharArray());
List<Integer> posB = kmp(text, b.toCharArray());
List<Integer> ans = new ArrayList<>();
int j = 0, m = posB.size();
for (int i : posA) {
while (j < m && posB.get(j) < i - k) {
j++;
}
if (j < m && posB.get(j) <= i + k) {
ans.add(i);
}
}
return ans;
}
// 双指针
public List<Integer> beautifulIndices2(String s, String a, String b, int k) {
char[] text = s.toCharArray();
List<Integer> posA = kmp(text, a.toCharArray());
List<Integer> posB = kmp(text, b.toCharArray());
List<Integer> ans = new ArrayList<>();
for (int i : posA) {
int bi = lowerBound(posB, i);
if (bi < posB.size() && posB.get(bi) - i <= k ||
bi > 0 && i - posB.get(bi - 1) <= k) {
ans.add(i);
}
}
return ans;
}
private List<Integer> kmp(char[] text, char[] pattern) {
int m = pattern.length;
int[] pi = new int[m];
int c = 0;
for (int i = 1; i < m; i++) {
char v = pattern[i];
while (c > 0 && pattern[c] != v) {
c = pi[c - 1];
}
if (pattern[c] == v) {
c++;
}
pi[i] = c;
}
List<Integer> res = new ArrayList<>();
c = 0;
for (int i = 0; i < text.length; i++) {
char v = text[i];
while (c > 0 && pattern[c] != v) {
c = pi[c - 1];
}
if (pattern[c] == v) {
c++;
}
if (c == m) {
res.add(i - m + 1);
c = pi[c - 1];
}
}
return res;
}
// 开区间写法
// 请看 https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(List<Integer> nums, int target) {
int left = -1, right = nums.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = (left + right) >>> 1;
if (nums.get(mid) < target) {
left = mid; // 范围缩小到 (mid, right)
} else {
right = mid; // 范围缩小到 (left, mid)
}
}
return right;
}
}
cpp 解法, 执行用时: 203 ms, 内存消耗: 86.4 MB, 提交时间: 2024-01-22 10:05:19
class Solution {
public:
// 二分
vector<int> beautifulIndices(string s, string a, string b, int k) {
vector<int> posA = kmp(s, a);
vector<int> posB = kmp(s, b);
vector<int> ans;
for (int i: posA) {
auto it = lower_bound(posB.begin(), posB.end(), i);
if (it != posB.end() && *it - i <= k ||
it != posB.begin() && i - *--it <= k) {
ans.push_back(i);
}
}
return ans;
}
// 双指针
vector<int> beautifulIndices2(string s, string a, string b, int k) {
vector<int> posA = kmp(s, a);
vector<int> posB = kmp(s, b);
vector<int> ans;
int j = 0, m = posB.size();
for (int i : posA) {
while (j < m && posB[j] < i - k) {
j++;
}
if (j < m && posB[j] <= i + k) {
ans.push_back(i);
}
}
return ans;
}
private:
vector<int> kmp(string &text, string &pattern) {
int m = pattern.length();
vector<int> pi(m);
int c = 0;
for (int i = 1; i < m; i++) {
char v = pattern[i];
while (c && pattern[c] != v) {
c = pi[c - 1];
}
if (pattern[c] == v) {
c++;
}
pi[i] = c;
}
vector<int> res;
c = 0;
for (int i = 0; i < text.length(); i++) {
char v = text[i];
while (c && pattern[c] != v) {
c = pi[c - 1];
}
if (pattern[c] == v) {
c++;
}
if (c == m) {
res.push_back(i - m + 1);
c = pi[c - 1];
}
}
return res;
}
};
python3 解法, 执行用时: 811 ms, 内存消耗: 52.1 MB, 提交时间: 2024-01-22 10:04:33
class Solution:
# 二分
def beautifulIndices2(self, s: str, a: str, b: str, k: int) -> List[int]:
pos_a = self.kmp(s, a)
pos_b = self.kmp(s, b)
ans = []
for i in pos_a:
bi = bisect_left(pos_b, i)
if bi < len(pos_b) and pos_b[bi] - i <= k or \
bi > 0 and i - pos_b[bi - 1] <= k:
ans.append(i)
return ans
# 双指针
def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
pos_a = self.kmp(s, a)
pos_b = self.kmp(s, b)
ans = []
j, m = 0, len(pos_b)
for i in pos_a:
while j < m and pos_b[j] < i - k:
j += 1
if j < m and pos_b[j] <= i + k:
ans.append(i)
return ans
def kmp(self, text: str, pattern: str) -> List[int]:
m = len(pattern)
pi = [0] * m
c = 0
for i in range(1, m):
v = pattern[i]
while c and pattern[c] != v:
c = pi[c - 1]
if pattern[c] == v:
c += 1
pi[i] = c
res = []
c = 0
for i, v in enumerate(text):
v = text[i]
while c and pattern[c] != v:
c = pi[c - 1]
if pattern[c] == v:
c += 1
if c == len(pattern):
res.append(i - m + 1)
c = pi[c - 1]
return res