<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]:
        # KMP algorithm
        # table that stores num of characters in pattern[0:j+1] that is both a prefix and suffix
        # if a string is both a prefix and a suffix then we can shift the window to the right and build on from that suffix
        # compare s[i] and a[j] and build the string a
            # when j == length of a, i-len(a)+1 is an index in s which is the start of str a
            # if s[i] != a[j], j = table[j-1]. until s[i] == a[j] or j == 0 (build a from start). if j == 0, i+=1
            # if s[i] == a[j], i+=1 j+=1
        # do the same for s and b

        # go through each index in s of a, check whether diff with index of b is <= k
            # if not
            # if index b greater, check next index of a
            # if index b smaller, check next index of b

        def prefix(a):
            m = len(a)
            j = 0
            table = [0]*len(a)

            for i in range(1,m):
                if a[j] == a[i]:
                    j += 1
                    table[i] = j
                else:
                    if j == 0:
                        continue
                    else:
                        j = table[j-1]

            return table

        def kmp(text,a):
            table = prefix(a)
            result = []
            m = len(a)
            n = len(text)
            i = j = 0

            while i <= n:
                if j == m:
                    result.append(i-m)
                    j = table[j-1]

                if i >= n:
                    break
                
                if text[i] == a[j]:
                    i += 1
                    j += 1
                else:
                    if j == 0:
                        i += 1
                    else:
                        j = table[j-1]

            return result

        first,second = kmp(s,a),kmp(s,b)
        print(first,second)
        i = j = 0
        result = []

        while i < len(first) and j < len(second):
            if abs(first[i]-second[j]) <= k:
                result.append(first[i])
                i += 1
            else:
                if second[j] > first[i]:
                    i += 1
                else:
                    j += 1

        return result

            


        



781