<p>You are given a <strong>0-indexed</strong> string <code>s</code>, a string <code>a</code>, a string <code>b</code>, and an integer <code>k</code>.</p>

<p>An index <code>i</code> is <strong>beautiful</strong> if:</p>

<ul>
	<li><code>0 &lt;= i &lt;= s.length - a.length</code></li>
	<li><code>s[i..(i + a.length - 1)] == a</code></li>
	<li>There exists an index <code>j</code> such that:
	<ul>
		<li><code>0 &lt;= j &lt;= s.length - b.length</code></li>
		<li><code>s[j..(j + b.length - 1)] == b</code></li>
		<li><code>|j - i| &lt;= k</code></li>
	</ul>
	</li>
</ul>

<p>Return <em>the array that contains beautiful indices in <strong>sorted order from smallest to largest</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcd&quot;, a = &quot;a&quot;, b = &quot;a&quot;, k = 4
<strong>Output:</strong> [0]
<strong>Explanation:</strong> There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == &quot;a&quot; and there exists an index 0 with s[0..0] == &quot;a&quot; and |0 - 0| &lt;= 4.
Thus we return [0] as the result.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>1 &lt;= a.length, b.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>s</code>, <code>a</code>, and <code>b</code> contain only lowercase English letters.</li>
</ul>

import bisect
from typing import List


# Brute-force substring matching.
# Time: O(xy + xz + xlogx), space: O(x + y + z),
# x = len(s), y = len(a), z = len(b)
class Solution0:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        def find_indices(text: str, pattern: str) -> List[int]:
            ret = []
            for i in range(len(text) - len(pattern) + 1):
                if text[i : i + len(pattern)] == pattern:
                    ret.append(i)
            return ret

        all_i, all_j = find_indices(s, a), find_indices(s, b)
        ret = []
        if len(all_i) == 0 or len(all_j) == 0:
            return []
        for i in all_i:
            closest = bisect.bisect_left(all_j, i)
            if closest == 0 and abs(all_j[closest] - i) <= k:
                ret.append(i)
            elif closest == len(all_j):
                if abs(all_j[closest - 1] - i) <= k:
                    ret.append(i)
            elif (
                abs(all_j[closest - 1] - i) <= k or abs(all_j[closest] - i) <= k
            ):
                ret.append(i)
        return ret


# KMP.
# Time: O(xy + xz + xlogx), space: O(x + y + z),
# x = len(s), y = len(a), z = len(b)
class Solution1:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        # This will lead to time complexity O(mn)
        # For example, text = "aaaaa", pattern = "aa"
        # For each round, kmp needs O(n)
        # We increment index by 1 -> need m iterations -> O(mn)
        def find_indices(text: str, pattern: str) -> List[int]:
            def compute_lps(pattern: str) -> List[int]:
                lps = [0] * len(pattern)
                lps_length, cur_index = 0, 1
                while cur_index < len(pattern):
                    if pattern[cur_index] == pattern[lps_length]:
                        lps_length += 1
                        lps[cur_index] = lps_length
                        cur_index += 1
                    elif lps_length == 0:
                        lps[cur_index] = 0
                        cur_index += 1
                    else:
                        lps_length = lps[lps_length - 1]
                return lps

            lps = compute_lps(pattern)

            def _kmp(text: str, pattern: str, start: int) -> int:
                text_index, pattern_index = start, 0
                while text_index < len(text):
                    if text[text_index] == pattern[pattern_index]:
                        text_index += 1
                        pattern_index += 1
                    elif pattern_index == 0:
                        text_index += 1
                    else:
                        pattern_index = lps[pattern_index - 1]
                    if pattern_index == len(pattern):
                        return text_index - pattern_index
                return -1

            def kmp(text: str, pattern: str) -> List[int]:
                start = 0
                res = []
                while (index := _kmp(text, pattern, start)) != -1:
                    res.append(index)
                    start = index + 1
                return res

            return kmp(text, pattern)

        all_i, all_j = find_indices(s, a), find_indices(s, b)
        ret = []
        if len(all_i) == 0 or len(all_j) == 0:
            return []
        for i in all_i:
            closest = bisect.bisect_left(all_j, i)
            if closest == 0 and abs(all_j[closest] - i) <= k:
                ret.append(i)
            elif closest == len(all_j):
                if abs(all_j[closest - 1] - i) <= k:
                    ret.append(i)
            elif (
                abs(all_j[closest - 1] - i) <= k or abs(all_j[closest] - i) <= k
            ):
                ret.append(i)
        return ret


# KMP finds all matches.
# Time: O(xy + xz + xlogx), space: O(x + y + z),
# x = len(s), y = len(a), z = len(b)
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        def kmp_all_matches(text: str, pattern: str) -> List[int]:
            def compute_lps(pattern: str) -> List[int]:
                lps = [0] * len(pattern)
                lps_length, cur_index = 0, 1
                while cur_index < len(pattern):
                    if pattern[cur_index] == pattern[lps_length]:
                        lps_length += 1
                        lps[cur_index] = lps_length
                        cur_index += 1
                    elif lps_length == 0:
                        lps[cur_index] = 0
                        cur_index += 1
                    else:
                        lps_length = lps[lps_length - 1]
                return lps

            lps = compute_lps(pattern)

            res = []
            text_index, pattern_index = 0, 0
            while text_index < len(text):
                if text[text_index] == pattern[pattern_index]:
                    text_index += 1
                    pattern_index += 1
                elif pattern_index == 0:
                    text_index += 1
                else:
                    pattern_index = lps[pattern_index - 1]
                if pattern_index == len(pattern):
                    res.append(text_index - pattern_index)
                    pattern_index = lps[pattern_index - 1]

            return res

        all_i, all_j = kmp_all_matches(s, a), kmp_all_matches(s, b)
        ret = []
        if len(all_i) == 0 or len(all_j) == 0:
            return []
        for i in all_i:
            closest = bisect.bisect_left(all_j, i)
            if closest == 0 and abs(all_j[closest] - i) <= k:
                ret.append(i)
            elif closest == len(all_j):
                if abs(all_j[closest - 1] - i) <= k:
                    ret.append(i)
            elif (
                abs(all_j[closest - 1] - i) <= k or abs(all_j[closest] - i) <= k
            ):
                ret.append(i)
        return ret


1034