TLE for C++ solution


#1

The code is here. I’m quite sure that the code is optimal, but it still gives TLE errors. Any comments?

int kmp(const string& s, const string& w) {
    vector<int> t;
    t.push_back(-1);
    int pos = 1;
    int cnd = 0;
    while (pos < w.size()) {
        t.push_back(cnd);
        while (cnd >= 0 && w[pos] != w[cnd])
            cnd = t[cnd];
        pos++;
        cnd++;
    }
    t.push_back(cnd);
    
    int j = 0;
    int k = 0;
    int count = 0;
    while (j < s.size()) {
        if (w[k] == s[j]) {
            j++;
            k++;
            if (k == w.size()) {
                count++;
                k = t[k];
            }
        } else {
            k = t[k];
            if (k < 0) {
                j++;
                k++;
            }
        }
    }
    return count;
}

int period(const string& s) {
    string dbl = s + s;
    dbl.pop_back();
    int count = kmp(dbl, s);
    return s.size() / count;
}

vector<int> sieve(200000, 1);
int Solution::solve(vector<string> &A) {

    set<int> periods;
    for (const string& s : A)
        periods.insert(period(s));
        
    vector<int> turns;
    for (const int p : periods) {
        for (int i = 1; i <= 200000; ++i) {
            if ((i * (i + 1)) % (2 * p) == 0) {
                turns.push_back(i);
                break;
            }
        }
    }

    static bool has_sieve = false;
    if (!has_sieve) {
        has_sieve = true;
        for (int i = 2; i <= 447; ++i) { // 447^2 ~= 200000
            if (sieve[i] > 1) continue;
            for (int j = i; j < 200000; j += i) {
                if (sieve[j] == 1)
                    sieve[j] = i;
            }
        }
    }

    unordered_map<int, int> powers;
    for (int n : turns) {
        unordered_map<int, int> p_row;
        while (n > 1) {
            int factor = sieve[n];
            p_row[factor]++;
            n /= factor;
        }
        
        for (auto item : p_row) {
            powers[item.first] = std::max(powers[item.first], item.second);
        }
    }

    const int64_t mod = 1000000007;
    int64_t result = 1;
    for (auto item : powers) {
        for (int i = 0; i < item.second; ++i)
            result = (result * item.first) % mod;
    }

    return result;
}