题意
题目大意是,给两个字符串 A 和 B,问 B 是否能成为 A+A+A+...+A 的子字符串,如果能的话,那么最少需要多少个 A?
暴力解法
直接 A+A+...,到哪次 A 包含 B 了,就返回 A 的个数。
但是 B 也可能不是 A 的拼接的子字符串,所以这种直观解法还是存在隐患(无限循环),最好还是动动脑筋。
动脑筋解法
假如 B 的长度为 b,A 的长度为 a,那么 n=Math.ceil(b/a) 一定意味着什么。但是到底 n 意味着什么呢?看看例子先。
假设 A=“abcdefg”, B="gab", n=Math.ceil(3/7) = 1, 这种情况下,B 是 A+A 的子字符串,也就是答案为 2,为 n+1;
假设 A=“ab”,B="abababa",n=Math.ceil(7/2) = 4,这种情况下,B 是 A+A+A+A 的子字符串,也就是答案为 4,为 n;
从上面两种情况看,答案通常为 n 或者 n+1。但是这两种情况是否涵盖了所有的情况呢?我们无法肯定。
我们可以提出假设,假设最终答案最小为 n(这一点很容易证明,不然 B 比 A 长,哪里能成为 A 的子字符串),最大为 n+1。
那么我们只需要证明第二点,通过反推,证明 答案大于等于 n+2 的时候,存在累赘的 A 就可以了。
如下图,假设 B 的长度是 A 的长度的 n 倍小一点。
如果答案为 n+2 的话,那么 B 在 A 的拼接字符串中的匹配情况应该如下图所示:
或者是
第一种情况,最前面那个 A 是多余的;第二种情况,最后面那个 A 是多余的。由此可以得出,如果存在答案,答案不会超过 n+1。
结论
这道题答案存在三种情况,假设 n = Math.ceil( B.length/A.length ),则
1. A 怎么拼接都不可能成为 B 的母串;
2. 答案为 n;
3. 答案为 n+1。
代码就不提供了,按照这种思路,很容易就可以解答出来的。