A lot of two way search...


  • 0
    K
    class Solution {
    public:
        int getMaxRepetitions(string s1, int n1, string s2, int n2) {
            int len = s1.size();
            if (len == 0) return 0;
            vector<vector<int>> wordIndex = vector<vector<int>>(26, vector<int>());
            for (int i = 0; i < len; ++i) {
                int ch = s1[i] - 'a';
                wordIndex[ch].push_back(i);
            }
            vector<vector<int>> nextIndex = vector<vector<int>>(26, vector<int>(100, -1));
    
            std::function<int(int, int)> getNextIndex = [&](int index, int ch) {
                if (index == len) {
                    index = 0;
                }
    
                if (nextIndex[ch][index] != -1) {
                    return nextIndex[ch][index];
                }
    
                int& ret = nextIndex[ch][index];
                if (wordIndex[ch].size() == 0) {
                    ret = -2;
                    return ret;
                }
    
                int l = 0, r = wordIndex[ch].size() - 1;
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (index <= wordIndex[ch][mid]) {
                        r = mid - 1;
                    }
                    else {
                        l = mid + 1;
                    }
                }
    
                if (l == wordIndex[ch].size()) {
                    l = wordIndex[ch][0];
                }
                else {
                    l = wordIndex[ch][l];
                }
    
                // Point to the next pos.
                // if l == size, means we will start next.
                l++;
    
                ret = l;
                return ret;
            };
    
            // Calculate the result.
            unordered_map<int, int> startIndexSet;
            vector<pair<int, int>> offset;
            int start = 0;
            while (true) {
                if (startIndexSet.find(start) != startIndexSet.end()) {
                    // Find a loop.
                    break;
                }
    
                startIndexSet[start] = offset.size();
    
                int cnt = 0;
                for (int i = 0; i < s2.size(); ++i) {
                    int ch = s2[i] - 'a';
                    int nextStart = getNextIndex(start, ch);
    
                    // printf("%d %d\n", wordIndex[ch][0], nextIndex[ch][start]);
                    // cout << s2[i] << " " << start << " " << nextStart << endl;
                    if (nextStart == -2) return 0;
                    if (nextStart <= start) {
                        cnt++;
                    }
    
                    start = nextStart;
                }
    
                offset.push_back(pair<int, int>(start, cnt));
            }
    
            int startIndex = startIndexSet[start];
            int t1 = 0;
            for (int i = 0; i < startIndex; ++i) {
                t1 += offset[i].second;
            }
    
            int t2 = 0;
            for (int i = startIndex; i < offset.size(); ++i) {
                t2 += offset[i].second;
            }
    
            // printf("%d %d %d\n", startIndex, t1, t2);
    
            std::function<bool(int)> canDo = [&](int m) {
                long long total = 1;
                long long c2 = n2*m;
                // printf("%lld\n", c2);
                if (c2 < startIndex) {
                    for (int i = 0; i < c2; ++i) {
                        total += offset[i].second;
                    }
    
                    return total <= n1;
                }
    
                c2 -= startIndex;
                total += t1;
    
                total += t2 * (c2 / (offset.size() - startIndex));
                int remain = c2 % (offset.size() - startIndex);
                for (int i = 0; i < remain; ++i) {
                    total += offset[i + startIndex].second;
                }
    
                // printf("%lld %d %d\n", total, n1, m);
                return total <= n1;
            };
    
            // Try to get the correct result of M.
            int l = 0, r = 1;
    
            while (canDo(r)) {
                r *= 2;
            }
    
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (canDo(mid)) {
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
    
            if (r < 0) r = 0;
            return r;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.