Find Beautiful Indices in the Given Array II

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.

Code

Time Complexity: $O(n)$, Space Complexity: $O(n)$

使用 kmp algorithm 找出所有子字串的位置，再用 two pointer 找到所有解。

比較特別的地方在於要用 kmp 找出所有子字串：

// continue searching
j = LPS[j - 1];

class Solution {
public:
    vector<int> beautifulIndices(string s, string a, string b, int k) {
        vector<int> res;
 
        vector<int> a1 = findAll(s, a);
        vector<int> b1 = findAll(s, b);
 
        int j = 0, n = b1.size();
        for(int i = 0; i < a1.size(); i++) {
            while(j < n && b1[j] <= a1[i] && (a1[i] - b1[j])> k) j++;
            if(j < n && abs(a1[i] - b1[j]) <= k) res.push_back(a1[i]);
        }
 
        return res;
    }
 
    vector<int> findAll(string s, string t) {
        int n = t.length();
        // build lps
        int i = 1, len = 0;
        vector<int> lps(n, 0);
        while(i < n) {
            if(t[i] == t[len]) {
                lps[i++] = ++len;
            } else {
                if(len == 0) i++;
                else len = lps[len - 1];
            }
        }
        vector<int> allindexes;
        int j = 0, m = s.length();
        i = 0;
        while(i < m) {
            if(s[i] == t[j]) {
                i++;
                j++;
                if(j == n) {
                    allindexes.push_back(i - j);
                    j = lps[j - 1];
                }
            } else {
                if(j == 0) i++;
                else j = lps[j - 1];
            }
        }
        return allindexes;
    }
 
 
};

Source

• Find Beautiful Indices in the Given Array II - LeetCode