题目描述
给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。
举个例子,A = “abcd”,B = “cdabcdab”。
答案为 3, 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为”abcdabcd”,B 并不是其子串。
思路
如果A的长度比B的长度小,那么A需要加大到至少比B的长度大,所以一开始在A长度比B长度小的时候,要不断加大A,并记录下加大的次数
当A的长度比B大时,先判断B是否是A的子串:
1如果是,则直接返回i
2如果不是,就把A再加大一次,再判断B是否是加大后的A的子串:
①如果是,返回i
②如果不是,则直接返回-1,因为在A第一次长度比B大的时候,有可能因为头尾没接上的原因使得B不是A的子串,在A又加大了一次后,解决了头尾没接上这个要素,所以如果此时B仍不是A的子串,那么无论A再怎么加,B都不可能是A的子串。
算法1
(暴力枚举) $O(n^2)$
时间复杂度
参考文献
C++ 代码
public:
int repeatedStringMatch(string A, string B) {
int i=1;
string s=A;
while(s.length()<B.length()) //当A长度比B小时,不断加长并记录i
{
i++;
s+=A;
}
if(s.find(B)!= s.npos) //A比B长后,第一次判断是否是子串
return i;
else
{
i++; //第二次判断是否是子串
s+=A;
if(s.find(B)!= s.npos)
return i;
else
return -1;
}
}
};