2024-05-18：用go语言，给定一个从 0 开始的字符串 s，以及两个子字符串 a 和 b，还有一个整数 k。
定义一个“美丽下标”，当满足以下条件时：
1.找到字符串 a 在字符串 s 中的位置，且该位置范围为 0 <= i <= s.length - a.length。
2.找到字符串 b 在字符串 s 中的位置，且该位置范围为 0 <= j <= s.length - b.length。
3.两个字符串的匹配位置之差的绝对值不超过 k。
需要按照美丽下标的大小升序排列，然后以数组的形式返回这些下标。
输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15。
输出：[16,33]。
答案2024-05-18：
chatgpt
题目来自leetcode3008。
大体步骤如下：
1.定义了 main 函数，其中给定了字符串 s、子字符串 a 和 b，以及整数 k。
2.在 main 函数中调用 beautifulIndices 函数，并输出结果。
3.beautifulIndices 函数中调用了 kmp 函数来找到字符串 a 和 b 在字符串 s 中的所有可能位置。
4.在 kmp 函数中，首先构建了 pattern 的前缀函数 pi。
5.对于子串 a，通过 KMP 算法寻找所有匹配的位置，将它们存储在 posA 中。
6.对于子串 b，同样使用 KMP 算法来寻找所有匹配的位置，将它们存储在 posB 中。
7.然后遍历 posA 中的每个位置 i，在 posB 中查找满足条件的位置 j 和 k，更新 ans。
8.将找到的美丽下标按照升序排列，并以数组形式返回。
总的时间复杂度：
- •KMP 算法的时间复杂度为 O(n + m)，其中 n 是字符串长度，m 是模式串长度。在该问题中，分别对两个子串执行 KMP 搜索，因此总的时间复杂度为 O(n + m) + O(n + m) = O(n + m)。
- •遍历 posA 和 posB 的时间复杂度为 O(n) + O(n) = O(n)，其中 n 是字符串长度。
总的额外空间复杂度：
- •在 KMP 函数中，构建了模式串的前缀函数 pi，使用了额外的空间来存储 pi 数组，其大小等于模式串的长度，因此空间复杂度为 O(m)。
- •在 beautifulIndices 函数中，存储了所有匹配的位置，即创建了 posA 和 posB 数组来存储这些位置，空间复杂度为 O(n)。
- •因此，总的额外空间复杂度为 O(m) + O(n)。
综上所述，总的时间复杂度为 O(n + m)，总的额外空间复杂度为 O(m) + O(n)。
Go完整代码如下：
packagemain
import"fmt"
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
}
funcmain(){
s:="isawsquirrelnearmysquirrelhouseohmy"
a:="my"
b:="squirrel"
k:=15
result:=beautifulIndices(s,a,b,k)
fmt.Println("Result:",result)
}
Python完整代码如下：
#-*-coding:utf-8-*-
defbeautiful_indices(s,a,b,k):
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
pos=[]
cnt=0
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
posA=kmp(s,a)
posB=kmp(s,b)
ans=[]
j,m=0,len(posB)
foriinposA:
whilejj+=1
ifjans.append(i)
returnans
s="isawsquirrelnearmysquirrelhouseohmy"
a="my"
b="squirrel"
k=15
result=beautiful_indices(s,a,b,k)
print("Result:",result)
热门跟贴