## Google Interview Question

Software Engineers**Country:**United States

```
public static void main(String[] args) {
String A = "abcd";
String B = "cdabcdabcdabcdab";
String temp = "";
int len = B.length() / A.length();
for(int i=0; i<len; i++) {
temp = temp + A;
}
while(len<=(B.length() / A.length() + 1)) {
if(temp.contains(B)) {
System.out.println(len);
break;
}else {
len++;
temp = temp+A;
}
}
}
```

If B matches repeated A that means B can be written as <S><A...><P> where <S> is any suffix of A including empty suffix, <A...> is A repeated some number of times including zero times and <P> is any prefix of A including empty prefix. Let len(A) = N, len(B) = M then ans is 1 (if non-empty S exists) + number of times A is repeated + 1 (if non-empty P exists):

- ashu1.220791 July 07, 2019<S> and <P> can be checked to exist in O(N*N) while individual <A> can be checked in N time and there might be at max ceil(M/N) times <A> in B.

If this pattern is not matched, return -1.