本文主要是介绍【教3妹学编程-算法题】3006. 找出数组中的美丽下标 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3妹：呜呜，烦死了， 脸上长了一个痘
2哥 : 不要在意这些细节嘛，不用管它，过两天自然不就好了。
3妹：切，你不懂，影响这两天的心情哇。
2哥 : 我看你是不急着找工作了啊， 工作那么辛苦，哪还有时间想这些啊。
3妹：说到找工作，我又要去刷题了。
2哥：我给你出一道关于美丽的题吧，让你的心情美丽美丽~
题目：
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标：
0 <= i <= s.length - a.length
s[i…(i + a.length - 1)] == a
存在下标 j 使得：
0 <= j <= s.length - b.length
s[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 <= 10^5
1 <= a.length, b.length <= 10
s、a、和 b 只包含小写英文字母。
思路：
KMP+二分查找，
用 KMP 求出 a 在 s 中的所有出现位置，记作 posA。
用 KMP 求出 b 在 s 中的所有出现位置，记作 posB。
遍历 posA中的下标 i，在 posB中二分查找离 iii 最近的 j。如果 ∣i−j∣≤k，则把 i 加入答案。
java代码：
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<>();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] >= targetint mid = (left + right) >>> 1;if (nums.get(mid) < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return right;}
}这篇关于【教3妹学编程-算法题】3006. 找出数组中的美丽下标 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
