3008-FindBeautifulIndicesInTheGivenArrayII.go

package main

// 3008. Find Beautiful Indices in the Given Array II
// You are given a 0-indexed string s, a string a, a string b, and an integer k.

// An index i is beautiful if:
//     0 <= i <= s.length - a.length
//     s[i..(i + a.length - 1)] == a
//     There exists an index j such that:
//         0 <= j <= s.length - b.length
//         s[j..(j + b.length - 1)] == b
//         |j - i| <= k

// Return the array that contains beautiful indices in sorted order from smallest to largest.

// Example 1:
// Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
// Output: [16,33]
// Explanation: There are 2 beautiful indices: [16,33].
// - The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
// - The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
// Thus we return [16,33] as the result.

// Example 2:
// Input: s = "abcd", a = "a", b = "a", k = 4
// Output: [0]
// Explanation: There is 1 beautiful index: [0].
// - The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
// Thus we return [0] as the result.

// Constraints:
//     1 <= k <= s.length <= 5 * 10^5
//     1 <= a.length, b.length <= 5 * 10^5
//     s, a, and b contain only lowercase English letters.

import "fmt"

func beautifulIndices(s string, a string, b string, k int) []int {
    sl := len(s)
    pat := func(pattern string) []int {
        n, l, i := len(pattern), 0 , 1
        res := make([]int, n)
        res[0] = 0
        for i < n {
            if pattern[i] == pattern[l] {
                l++
                res[i] = l
                i++
            } else {
                if l != 0 {
                    l = res[l-1]
                } else {
                    res[i] = l
                    i++
                }
            }   
        }
        return res
    }
    kmp := func(pat string, lps []int) []int {
        res, i, j, n := []int{}, 0, 0, len(pat)
        for sl - i >= n - j {
            if s[i] == pat[j] {
                i++
                j++
            }
            if j == n {
                res = append(res, i - n)
                j = lps[j - 1]
            } else if s[i] != pat[j] {
                if j!=0 {
                    j = lps[j - 1]
                } else {
                    i++
                }
            }
        }
        return res
    }
    res, indexA, indexB := []int{}, kmp(a, pat(a)), kmp(b, pat(b))
    i, j := 0, 0
    for i < len(indexA) && j < len(indexB) {
        if indexA[i] + k >= indexB[j] && indexA[i] - k <= indexB[j] {
            res = append(res, indexA[i])
            i++
        } else if indexA[i] - k > indexB[j] {
            j++
        } else {
            i++
        }
    }
    return res
}

func main() {
    // Example 1:
    // Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
    // Output: [16,33]
    // Explanation: There are 2 beautiful indices: [16,33].
    // - The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
    // - The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
    // Thus we return [16,33] as the result.
    fmt.Println(beautifulIndices("isawsquirrelnearmysquirrelhouseohmy", "my" ,"squirrel", 15)) // [16,33]
    // Example 2:
    // Input: s = "abcd", a = "a", b = "a", k = 4
    // Output: [0]
    // Explanation: There is 1 beautiful index: [0].
    // - The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
    // Thus we return [0] as the result.
    fmt.Println(beautifulIndices("abcd", "a" ,"a", 4)) // [0]

    // fmt.Println(beautifulIndices1("isawsquirrelnearmysquirrelhouseohmy", "my" ,"squirrel", 15)) // [16,33]
    // fmt.Println(beautifulIndices1("abcd", "a" ,"a", 4)) // [0]
}