# 3ms C++ O(n) solution

• ``````class Solution {
public:
int repeatedStringMatch(string A, string B) {
int i = 0, j = 0, count = 1;
while(j < B.size()){
while(i < A.size() && A[i] != B[j]) i++;
if(i == A.size() || count > 1) return -1;
while(j < B.size() && A[i++] == B[j++]){
if(j == B.size()) return count;
if(i == A.size()) i = 0, count++;
}
j = 0;
}
}
};
``````

Update:

``````class Solution {
public:
int repeatedStringMatch(string A, string B) {
if(B.empty()) return 1;
for(int i = 0, j = 0; j < B.size() && i < A.size(); i++, j = 0){
while(i < A.size() && A[i] != B[j]) i++;
int k = i, count = 1;
while(A[k++] == B[j++]){
if(j == B.size()) return count;
if(k == A.size()) k = 0, count++;
}
}
return -1;
}
};
``````

• failed at
A = "aaab"
B = "aab"

we should add this test case into OJ

@zefengsong said in 3ms C++ O(n) solution:

class Solution {
public:
int repeatedStringMatch(string A, string B) {
int i = 0, j = 0, count = 1;
while(j < B.size()){
while(i < A.size() && A[i] != B[j]) i++;
if(i == A.size() || count > 1) return -1;
while(j < B.size() && A[i++] == B[j++]){
if(j == B.size()) return count;
if(i == A.size()) i = 0, count++;
}
j = 0;
}
}
};

• @jordandong You are right, thx for pointing out. How about the updated one?

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