3008. Find Beautiful Indices in the Given Array II

Problem Link

Description

---

You are given a 0-indexed string s, a string a, a string b, and an integer k.

An index i is beautiful if:

• 0 <= i <= s.length - a.length
• s[i..(i + a.length - 1)] == a
• There exists an index j such that:
  • 0 <= j <= s.length - b.length
  • s[j..(j + b.length - 1)] == b
  • |j - i| <= k

Return the array that contains beautiful indices in sorted order from smallest to largest.

 

Example 1:

Input: s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15
Output: [16,33]
Explanation: There are 2 beautiful indices: [16,33].
- The index 16 is beautiful as s[16..17] == "my" and there exists an index 4 with s[4..11] == "squirrel" and |16 - 4| <= 15.
- The index 33 is beautiful as s[33..34] == "my" and there exists an index 18 with s[18..25] == "squirrel" and |33 - 18| <= 15.
Thus we return [16,33] as the result.

Example 2:

Input: s = "abcd", a = "a", b = "a", k = 4
Output: [0]
Explanation: There is 1 beautiful index: [0].
- The index 0 is beautiful as s[0..0] == "a" and there exists an index 0 with s[0..0] == "a" and |0 - 0| <= 4.
Thus we return [0] as the result.

 

Constraints:

• 1 <= k <= s.length <= 5 * 105
• 1 <= a.length, b.length <= 5 * 105
• s, a, and b contain only lowercase English letters.

Solution

---

Python3

def rabin_karp(s, t):
    p = 31
    m = 10 ** 9 + 9
    S, T = len(s), len(t)
    
    p_pow = [0] * max(S, T)
    p_pow[0] = 1
    for i in range(1, len(p_pow)):
        p_pow[i] = (p_pow[i - 1] * p) % m
    
    h = [0] * (T + 1)
    for i in range(T):
        h[i + 1] = (h[i] + (ord(t[i]) - ord('a') + 1) * p_pow[i]) % m
    
    h_s = 0
    for i in range(S):
        h_s = (h_s + (ord(s[i]) - ord('a') + 1) * p_pow[i]) % m
    
    occurences = []
    for i in range(T - S + 1):
        cur_h = (h[i + S] + m - h[i]) % m
        if cur_h == h_s * p_pow[i] % m:
            occurences.append(i)
    
    return occurences
 
class Solution:
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        N = len(s)
        A = rabin_karp(a, s)
        B = rabin_karp(b, s)
        res = []
        
        for ai in A:
            index = bisect_right(B, ai)
            
            if index < len(B) and abs(B[index] - ai) <= k:
                res.append(ai)
            elif index - 1 >= 0 and abs(B[index - 1] - ai) <= k:
                res.append(ai)
        
        return res
        

C++

vector<int> rabin_karp(string const& s, string const& t) {
    const int p = 31; 
    const int m = 1e9 + 9;
    int S = s.size(), T = t.size();
 
    vector<long long> p_pow(max(S, T)); 
    p_pow[0] = 1; 
    for (int i = 1; i < (int)p_pow.size(); i++) 
        p_pow[i] = (p_pow[i-1] * p) % m;
 
    vector<long long> h(T + 1, 0); 
    for (int i = 0; i < T; i++)
        h[i+1] = (h[i] + (t[i] - 'a' + 1) * p_pow[i]) % m; 
    long long h_s = 0; 
    for (int i = 0; i < S; i++) 
        h_s = (h_s + (s[i] - 'a' + 1) * p_pow[i]) % m; 
 
    vector<int> occurrences;
    for (int i = 0; i + S - 1 < T; i++) {
        long long cur_h = (h[i+S] + m - h[i]) % m;
        if (cur_h == h_s * p_pow[i] % m)
            occurrences.push_back(i);
    }
    return occurrences;
}
 
class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        int N = s.length();
        vector<int> A = rabin_karp(a, s);
        vector<int> B = rabin_karp(b, s);
        vector<int> res;
        
        for (int ai : A) {
            auto it = upper_bound(B.begin(), B.end(), ai);
            if (it != B.end() && abs(*it - ai) <= k) {
                res.push_back(ai);
            } else if (it != B.begin() && abs(*prev(it) - ai) <= k) {
                res.push_back(ai);
            }
        }
        
        return res;
    }
};