原題：

力扣鏈接:686. 重復疊加字符串匹配

題目簡述：

給定兩個字符串 a 和 b，尋找重復疊加字符串 a 的最小次數，使得字符串 b 成為疊加后的字符串 a 的子串，如果不存在則返回 -1。

注意：字符串 “abc” 重復疊加 0 次是 “”，重復疊加 1 次是 “abc”，重復疊加 2 次是 “abcabc”。

解題思路

審題提煉

1.匹配子串，使用find函數實現子串查找；
2.然后循環疊加，找到退出循環的判據（這步倒騰很久都沒倒騰出來，哎，提交了好幾次都失敗了），實現找不到子串的情況的退出；

波折心路（地鐵上手機刷題）：

1.自己的退出循環的判據一直錯，搗鼓半天一直錯，最后沒辦法，只能直奔題解區了。
2.看了官方的題解云里霧里，和我的方法有出入啊，于是又翻了翻，最終找到了和我思路類似的大佬的題解。看了大佬的題解豁然開朗，果斷運行一波，如絲般潤滑。
3.奉上大佬鏈接：
關鍵是找到循環終止條件

如果n個A字符串能包含B字符串，可能有幾種情況：
1、A = “ab”, B = “abab”,循環n個A，剛好包含B；
2、A = “ab”, B = “ababa”,那么需要循環n + 1次；
3、A = “ab”, B = “babab”，那么需要循環n + 1次；
4、A = “ab”, B = “bababa”，那么需要循環n + 1次；
如果B不滿足以上情況，A再怎么循環也是白搭，比如，A = “ab”, B = “bababb”，循環多少次都只是浪費。
因此，如果B能夠在A的N次循環中被找到，最多只需要循環n+2次。循環終止條件就是累積的字符串長度 > (n + 2) * sizeA = (sizeB/sizeA + 2) * sizeA= sizeB + 2*sizeA.

4.over;

C++代碼：

class Solution { public:int repeatedStringMatch(string a, string b) {int na = a.size();int nb = b.size();string aa;int naa = 0;int i = 0;while(1){if(aa.find(b) != -1){return i;}i++;aa += a;naa =aa.size();if(naa > 2*na + nb)return -1;} return -1;} };

力扣結果展示：

總結

以上是生活随笔為你收集整理的【快乐水题】686. 重复叠加字符串匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。