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

class Solution:
    def build_lps(self, pattern):
        lps = [0] * len(pattern)
        i, length = 1, 0

        while i < len(pattern):
            # check if pattern[i] == pattern[length]
            # if so, length += 1
            # i += 1
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1

            # if pattern[i] != pattern[length] and length > 0:
            # backtrack (length = lps[length - 1])
            elif length > 0:
                length = lps[length - 1]

            # else:
            # move i forward
            # set lps[i] = 0 because there is no match
            else:
                lps[i] = 0
                i += 1
        
        return lps
    
    def KMP(self, pattern, text):
        lps = self.build_lps(pattern)
        i, j = 0, 0
        res = []

        while j < len(text):
            # if pattern[i] == text[j]:
            # increment both i and j
            if pattern[i] == text[j]:
                i += 1
                j += 1

            # if i == len(pattern) (i.e. we've found the whole pattern)
            # add j - i to the res
            if i == len(pattern):
                res.append(j - i)
                i = lps[i - 1] # backtrack to find the pattern again

            # elif j < len(text) and pattern[i] != text[j]
            # set i = lps[i - 1] if i != 0
            # otherwise, increment j by 1
            elif j < len(text) and pattern[i] != text[j]:
                if i != 0:
                    i = lps[i - 1] #backtrack to find a potential different match
                else:
                    j += 1
            
        return res

    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        a_ind = self.KMP(a, s)
        b_ind = self.KMP(b, s)

        res = []
        j = 0
        print(a_ind, b_ind)

        for i in range(len(a_ind)):
            while j < len(b_ind) and b_ind[j] < a_ind[i] - k:
                j += 1
            if j < len(b_ind) and abs(b_ind[j] - a_ind[i]) <= k:
                res.append(a_ind[i])
        
        return res
        


# ''''
# this could be done in O(n) using KMP
# two passes:
# 1. KMP on string a
# 2. KMP on string b

# previously we did this brute force, going through every index i and per i going through every index j and checking. 

# - binary search .1.1.1./1!!?!?!?/1
# - i forgot we have to use kmp lol
        
1114