宁波网站推广厂家电话,响应式个人网站模板,wordpress ciphpdown,深圳品牌策划公司排行榜3妹#xff1a;呜呜#xff0c;烦死了#xff0c; 脸上长了一个痘 2哥 : 不要在意这些细节嘛#xff0c;不用管它#xff0c;过两天自然不就好了。 3妹#xff1a;切#xff0c;你不懂#xff0c;影响这两天的心情哇。 2哥 : 我看你是不急着找工作了啊#xff0c; 工作… 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 5 * 10^5 1 a.length, b.length 5 * 10^5 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 ListInteger beautifulIndices(String s, String a, String b, int k) {char[] text s.toCharArray();ListInteger posA kmp(text, a.toCharArray());ListInteger posB kmp(text, b.toCharArray());ListInteger 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 ListInteger 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;}ListInteger 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(ListInteger 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;}
}
