模拟法
下界：复制后的a的长度必须大于等于b的长度
上界：下界+1(因为原字符串长度可能大于下界-1但小于下界，所以不能保证b的结尾可以具备使用a中所有字符的能力，因此多复制一个可以保证a中所有字符都作为b的开头和结尾)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int repeatedStringMatch(string a, string b) {
int m = a.size(), n = b.size();
int c = 0;
string tmp;
while(tmp.size() < b.size() && ++c)
tmp += a;
tmp += a;
int pos = tmp.find(b, 0);
if(pos == std::string::npos)
return -1;
if(pos + n - 1 < m * c)
return c;
return c + 1;
}
};
|
kmp
一文详解 KMP 算法
字符串哈希