2024-05-11：用go语言，给定一个从零开始索引的字符串 s， 以及

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是字符串的长度。这是因为在KMP算法中，构建前缀表和匹配过程都需要线性时间。

s

总的空间复杂度为O(m)，其中m是字符串的长度。这是因为在KMP算法中需要使用一个长度为m的前缀表来存储匹配的信息。

b

Go完整代码如下：

packagemain
import"fmt"
funcmain(){
s:="isawsquirrelnearmysquirrelhouseohmy"
a:="my"
b:="squirrel"
k:=15
ans:=beautifulIndices(s,a,b,k)
fmt.Println(ans)
}
funcbeautifulIndices(s,a,bstring,kint)(ans[]int){
posA:=kmp(s,a)
posB:=kmp(s,b)
j,m:=0,len(posB)
for_,i:=rangeposA{
forjj++
}
ifjans=append(ans,i)
}
}
return
}
funckmp(text,patternstring)(pos[]int){
m:=len(pattern)
pi:=make([]int,m)
cnt:=0
fori:=1;iv:=pattern[i]
forcnt>0&&pattern[cnt]!=v{
cnt=pi[cnt-1]
}
ifpattern[cnt]==v{
cnt++
}
pi[i]=cnt
}
cnt=0
fori,v:=rangetext{
forcnt>0&&pattern[cnt]!=byte(v){
cnt=pi[cnt-1]
}
ifpattern[cnt]==byte(v){
cnt++
}
ifcnt==m{
pos=append(pos,i-m+1)
cnt=pi[cnt-1]
}
}
return
}
funcabs(xint)int{
ifx<0{
return-x
}
returnx
}

Python完整代码如下：

#-*-coding:utf-8-*-
defmain():
s="isawsquirrelnearmysquirrelhouseohmy"
a="my"
b="squirrel"
k=15
ans=beautiful_indices(s,a,b,k)
print(ans)
defbeautiful_indices(s,a,b,k):
posA=kmp(s,a)
posB=kmp(s,b)
j,m=0,len(posB)
ans=[]
foriinposA:
whilejj+=1
ifjans.append(i)
returnans
defkmp(text,pattern):
m=len(pattern)
pi=[0]*m
cnt=0
foriinrange(1,m):
v=pattern[i]
whilecnt>0andpattern[cnt]!=v:
cnt=pi[cnt-1]
ifpattern[cnt]==v:
cnt+=1
pi[i]=cnt
cnt=0
pos=[]
fori,vinenumerate(text):
whilecnt>0andpattern[cnt]!=v:
cnt=pi[cnt-1]
ifpattern[cnt]==v:
cnt+=1
ifcnt==m:
pos.append(i-m+1)
cnt=pi[cnt-1]
returnpos
defabs(x):
ifx<0:
return-x
returnx
main()