Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.
For example, with A = "abcd" and B = "cdabcdab".
Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").
Note:
The length of
The length of
A and B will be between 1 and 10000.为满足包含B的条件，A最多重复的次数不会超过B.length() + A.length() * 2
Solution #1, 暴力解
注意返回时的count的计算
O(m * n)
class Solution {
public int repeatedStringMatch(String A, String B) {
String s = A;
while (s.length() <= B.length() + A.length()) {
s += A;
}
for (int i = 0; i < s.length() - B.length() + 1; i++) {
String sub = s.substring(i, i + B.length());
if (sub.equals(B)) {
return (i + B.length() + A.length() - 1) / A.length();
}
}
return -1;
}
}
Solution #2, 典型的KMP
理解的要点
1. 找每个点的longest proper preffix == longest proper suffix (proper的意思是string本身不能算＊ffix)
2. preprocess里是pattern自己比自己。主方法里是pattern对比A。2者的原理其实是一样的。
3. table里存的是proper的长度
class Solution {
public int repeatedStringMatch(String A, String pattern) {
int i = 0, j = 0;
int[] table = preprocess(pattern);
String s = A;
while (s.length() < pattern.length() + A.length()) {
s += A;
}
while (i < s.length()) {
if (s.charAt(i) == pattern.charAt(j)) {
j++;
i++;
if (j == pattern.length()) break;
}else if (j > 0) {
j = table[j - 1];
}else {
i++;
}
}
System.out.println(i);
if (i == s.length()) return -1;
return (i + A.length() - 1) / A.length();
}
private int[] preprocess(String s) {
int[] table = new int[s.length()];
int j = 0, i = 1;
while (i < s.length()) {
if (s.charAt(j) == s.charAt(i)) {
table[i] = j + 1;
j++;
i++;
}else if (j > 0) {
j = table[j - 1];
}else {
i++;
}
}
return table;
}
}
