2024-05-11:用go语言,给定一个从零开始索引的字符串 s,
以及两个字符串 a 和 b,还有一个整数 k。
定义美丽下标为满足特定条件的字符串下标。
需要找到所有美丽下标,按升序排列后返回为数组形式。
输入:s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15。
输出:[16,33]。
答案2024-05-11:
chatgpt
题目来自leetcode3006。
1.定义一个函数beautifulIndices
,接受参数为字符串s
,字符串a
,字符串b
和整数k
,并返回一个整数数组ans
。
2.在函数beautifulIndices
中,首先调用函数kmp
找到字符串s
中满足字符串a
的子串的下标位置,将结果保存在变量posA
中。
3.接下来,利用函数kmp
找到字符串s
中满足字符串b
的子串的下标位置,将结果保存在变量posB
中。
4.初始化变量j
和m
,分别表示在posB
中进行遍历的指针和posB
的长度。
5.遍历posA
中的每个下标i
,在内部循环中,检查posB
中从j
开始的元素是否小于i-k
。如果满足条件,则将j
自增。
6.如果j
仍然小于m
,并且满足posB[j] - i
的绝对值小于等于k
,则将i
添加到结果数组ans
中。
7.最后,将结果数组ans
返回。
总的时间复杂度为O(n),其中n是字符串s
的长度。这是因为在KMP算法中,构建前缀表和匹配过程都需要线性时间。
总的空间复杂度为O(m),其中m是字符串b
的长度。这是因为在KMP算法中需要使用一个长度为m的前缀表来存储匹配的信息。
package main
import "fmt"
func main() {
s := "isawsquirrelnearmysquirrelhouseohmy"
a := "my"
b := "squirrel"
k := 15
ans := beautifulIndices(s, a, b, k)
fmt.Println(ans)
}
func beautifulIndices(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 && abs(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
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
# -*-coding:utf-8-*-
def main():
s = "isawsquirrelnearmysquirrelhouseohmy"
a = "my"
b = "squirrel"
k = 15
ans = beautiful_indices(s, a, b, k)
print(ans)
def beautiful_indices(s, a, b, k):
posA = kmp(s, a)
posB = kmp(s, b)
j, m = 0, len(posB)
ans = []
for i in posA:
while j < m and posB[j] < i - k:
j += 1
if j < m and abs(posB[j] - i) <= k:
ans.append(i)
return ans
def kmp(text, pattern):
m = len(pattern)
pi = [0] * m
cnt = 0
for i in range(1, m):
v = pattern[i]
while cnt > 0 and pattern[cnt] != v:
cnt = pi[cnt-1]
if pattern[cnt] == v:
cnt += 1
pi[i] = cnt
cnt = 0
pos = []
for i, v in enumerate(text):
while cnt > 0 and pattern[cnt] != v:
cnt = pi[cnt-1]
if pattern[cnt] == v:
cnt += 1
if cnt == m:
pos.append(i - m + 1)
cnt = pi[cnt-1]
return pos
def abs(x):
if x < 0:
return -x
return x
main()