<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]:
        #i is beaitufl if s[i:i + a.length - 1] == a (start of a in S)
        #exists a j s.t. j is the start of b in S 
        #return all i where there is j within distance k of i 

        def get_indexes(pattern, base=26, prime=100000687):
            #Get hash for our pattern string 
            length = len(pattern)
            p_ = pow(base, length - 1, prime) #b^n-1

            target = 0
            for elem in pattern:
                target *= base #multiply all old terms by base to shift them 
                target += (ord(elem) - 96) 
                target %= prime

            #Now, find instances of our pattern in text string 
            res = []
            current = 0
            for index, right in enumerate(s):
                if index >= length: 
                    left = s[index - length]
                    current -= (ord(left) - 96) * p_ 
                
                current *= base #shift
                current += (ord(s[index]) - 96) 
                current %= prime 
                if current == target:
                    res.append(index - length + 1)
            return res 

        eyes = get_indexes(a)
        jays = get_indexes(b)
        # i = 0
        # while i < len(s):
        #     val = s.find(a, i) 
        #     if val == -1:
        #         break 
        #     eyes.append(val)
        #     i = val + 1 

        # j = 0
        # while j < len(s):
        #     val = s.find(b, j) 
        #     if val == -1:
        #         break 
        #     jays.append(val)
        #     j = val + 1 
        

        res = []
        for i in eyes:
            low = 0
            high = len(jays) - 1 
            while low <= high:
                mid = (low + high) // 2 
                if -1 * k <= jays[mid] - i <= k:
                    res.append(i)
                    break 
                elif jays[mid] > i:
                    high = mid - 1 
                else:
                    low = mid + 1 
        return res 


        
1446