<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>

from bisect import bisect_left

class Solution:
    def computeLPSArray(self, pat):
        M = len(pat)
        lps = [0] * M
        
        # Length of the previous longest prefix suffix
        length = 0  
        i = 1

        # Loop calculates lps[i] for i = 1 to M-1
        while i < M:
            if pat[i] == pat[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps


    def KMPSearch(self, pat, txt):
        M = len(pat)
        N = len(txt)

        # Create lps[] that will hold the longest prefix
        # suffix values for pattern
        lps = self.computeLPSArray(pat)
        result = []

        i = 0  # index for txt
        j = 0  # index for pat
        while (N - i) >= (M - j):
            if pat[j] == txt[i]:
                j += 1
                i += 1

            if j == M:
                result.append(i - j + 1)
                j = lps[j - 1]
            elif i < N and pat[j] != txt[i]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return [i-1 for i in result]


    def get_indices_of_substring_in_string(self, s: str, x: str) -> List[int]:
        # return [i for i in range(len(s)) if s[i:i+len(x)] == x]
        beautiful_indices = []
        s_idx = 0
        x_idx = 0
        iters = 0
        while s_idx < len(s):
            # if iters > 30:
            #     break
            # iters += 1
            # print(s_idx)
            if s[s_idx] == x[x_idx]:
                x_idx += 1
                s_idx += 1
                if x_idx == len(x):
                    beautiful_indices.append(s_idx - x_idx)
                    x_idx = 0
                    # if s_idx != prev_s_idx:
                    #     s_idx -= 1
                    #     prev_s_idx = s_idx
            else:
                x_idx = 0
                if s_idx != prev_s_idx:
                    s_idx -= 1
                    prev_s_idx = s_idx
                    
        return beautiful_indices


    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        a_indices = self.KMPSearch(a, s)
        b_indices = self.KMPSearch(b, s)
        print(a_indices, b_indices)
        if len(a_indices) == 0 or len(b_indices) == 0:
            return []

        beautiful_indices = []
        a_ptr = b_ptr = 0
        # for a_ptr in a_indices:
        #     b_ptr = bisect_left(b_indices, a_ptr - k)
        #     while b_ptr < len(b_indices) and b_indices[b_ptr] <= a_ptr + k:
        #         if a_ptr - k <= b_indices[b_ptr]:
        #             beautiful_indices.append(a_ptr)
        #             break
        #         b_ptr += 1
        
        # return beautiful_indices
        while a_ptr < len(a_indices):
            if b_indices[b_ptr] < a_indices[a_ptr] - k:
                if b_ptr == len(b_indices) - 1:
                    a_ptr += 1
                else:
                    b_ptr += 1
            elif b_indices[b_ptr] > a_indices[a_ptr] + k:
                a_ptr += 1
            else:
                beautiful_indices.append(a_indices[a_ptr])
                a_ptr += 1
        return beautiful_indices
941