C++ 3ms using the doubling table


  • 0
    L
    pair<int, int> d[20][110];
    class Solution {
    public:
        int getMaxRepetitions(const string &s1, int n1, string s2, int n2) {
            if (n1 == 0 || n2 == 0 || s1.empty() || s2.empty())
                return 0;
            int len = s2.size();
    
            // calculate the transitions in one step
            for (int i = 0; i < len; ++i) {
                int j = i, cnt = 0;
                for (char c : s1)
                    if (c == s2[j] && ++j == len) {
                        cnt++;
                        j = 0;
                    }
                d[0][i] = {j, cnt};
            }
    
            // calculate the doubling table
            for (int i = 1; i < 20; ++i)
                for (int j = 0; j < len; ++j) {
                    int t = d[i - 1][j].first;
                    d[i][j].first = d[i-1][t].first;
                    d[i][j].second = d[i-1][j].second + d[i-1][t].second;
                }
    
            // advance n1 steps with doubling
            int cnt = 0;
            for (int i = 19, j = 0; n1 && i >= 0; --i)
                if ((1 << i) <= n1) {
                    n1 -= 1 << i;
                    cnt += d[i][j].second;
                    j = d[i][j].first;
                }
            return cnt / n2;
        }
    };
    

Log in to reply
 

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