2024-05-11：用go语言，给定一个从零开始索引的字符串 s， 以及两个字符串 a 和 b，还有一个整数 k。 定义美丽下

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的前缀表来存储匹配的信息。

Go完整代码如下：

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

}

在这里插入图片描述Python完整代码如下：

# -*-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()

在这里插入图片描述