<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 beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        if len(a) > len(s) or len(b) > len(s):
            return []
        BASE = 29
        MOD = 1000000007
        def getHash(haystack, start, end):
            hash_val = 0
            for i in range(start, end):
                hash_val = hash_val * BASE % MOD + (ord(haystack[i])-96)
                hash_val = hash_val % MOD

            return hash_val

        def getIndicies(needle):
            indicies = []
            needle_hash = getHash(needle, 0, len(needle))
            #print("needle hash: ", needle_hash, needle)
            curr_hash = getHash(s, 0, len(needle))
            #print("curr hash: ", curr_hash, s[0:len(needle)])
            p_power = pow(BASE, len(needle)-1, MOD)

            #print("h")
            #print(getHash("sa", 0, 2))
            if needle_hash == curr_hash:
                indicies.append(0)

            for i in range(len(needle), len(s)):
                prev_char_val = ord(s[i-len(needle)]) - 96
                # subtract out left
                curr_hash = (curr_hash - prev_char_val * p_power % MOD) % MOD

                # mulitply everything by BASE
                curr_hash = curr_hash * BASE % MOD

                # add right most character
                curr_hash = (curr_hash + (ord(s[i])-96)) % MOD


                if curr_hash == needle_hash:
                    indicies.append(i-len(needle)+1)
            return indicies
        
        ans = []
        a_indicies = getIndicies(a)
        b_indicies = getIndicies(b)

        a_p, b_p = 0, 0
        while a_p < len(a_indicies) and b_p < len(b_indicies):
            if abs(a_indicies[a_p]-b_indicies[b_p]) <= k:
                ans.append(a_indicies[a_p])
                a_p += 1
            else:
                if a_indicies[a_p] < b_indicies[b_p]:
                    a_p += 1
                else:
                    b_p += 1
                

        #print(a_indicies)
        #print(b_indicies)
        return ans




        
1273