2024-05-18：用 go 语言，给定一个从 0 开始的字符串 s，以及两个子字符串 a 和 b，还有一个整数 k。定义一个“美丽下标”，当满足以下条件时： 1. 找到字符串 a 在字符串 s 中的位

作者：福大大架构师每日一题

2024-05-18
北京
本文字数：2001 字
阅读完需：约 7 分钟

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 完整代码如下：

package main
import "fmt"
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 && 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 main() {    s := "isawsquirrelnearmysquirrelhouseohmy"    a := "my"    b := "squirrel"    k := 15
    result := beautifulIndices(s, a, b, k)    fmt.Println("Result:", result)}

复制代码

Python 完整代码如下：

# -*-coding:utf-8-*-
def beautiful_indices(s, a, b, k):    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
        pos = []        cnt = 0        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
    posA = kmp(s, a)    posB = kmp(s, b)
    ans = []    j, m = 0, len(posB)    for i in posA:        while j < m and posB[j] < i - k:            j += 1        if j < m and posB[j] <= i + k:            ans.append(i)
    return ans
s = "isawsquirrelnearmysquirrelhouseohmy"a = "my"b = "squirrel"k = 15
result = beautiful_indices(s, a, b, k)print("Result:", result)