C++ Algorithm to Check if a String is Repeated

Given a string s, return whether it’s a repeating string.

Constraints
n ≤ 100,000 where n is the length of s
Example 1

Input
s = “dogdogdog”
Output
true

Explanation
“dog” is repeated.

Example 2
Input
s = “catdog”
Output
false

Repeated String Check in C++

The strategy is to partition the string into size 1, 2, 3 .. until n/2 where n is the size of the string. Also, we can skip the parition that n%j is not zero.

bool solve(string s) {
    if (s.empty()) return false;
    for (int j = 1; (j <= s.size() / 2); ++ j) {
        if (s.size() % j != 0) continue;
        bool flag = true;
        for (int i = j; i < s.size(); ++ i) {
            if (s[i] != s[i - j]) {
                flag = false;
                break;
            }
        }
        if (flag) return true;
    }
    return false;
}

Then, we can check the characters for equality of the neighbour parition. The time complexity is O(NM) where N is the number of characters in the string and M is the number of divisors for N.

–EOF (The Ultimate Computing & Technology Blog) —