Dadas dos cadenas A y B, encuentre el número mínimo de veces que A debe repetirse de manera que B sea una subcadena de la misma. Si no hay tal solución, devuelve -1.
Por ejemplo, con A = «abcd» y B = «cdabcdab».
Retorna 3, porque al repetir A tres veces (“abcdabcdabcd”), B es una subcadena de la misma; y B no es una subcadena de A repetida dos veces («abcdabcd»).
Nota:
La longitud de A y B estará entre 1 y 10000.
Solución Java
La complejidad temporal de la solución óptima es O (n) donde n es la longitud de la cuerda más larga de A y B.
public int repeatedStringMatch(String A, String B) { int i = 0; int j = 0; int result = 0; int k = 0; while (j < B.length()) { if (A.charAt(i) == B.charAt(j)) { i++; j++; if (i == A.length()) { i = 0; result++; } } else { k++; if (k == A.length()) { return -1; } i = k; j = 0; result = 0; } } if (i > 0) { result++; } return result; } |
