每日一题——686. 重复叠加字符串匹配

686. 重复叠加字符串匹配

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

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

public class Solution {
    public int RepeatedStringMatch(string a, string b) {
        
        string A = a;
        int ans = 1;
        int maxLength = 2*a.Length + b.Length;
        while(a.Length <= maxLength)
        {
            if(a.IndexOf(b) != -1)
            {
                return ans;
            }
            else
            {
                a += A;
                ans++;
            }
        }

        return -1;
    }
}

我的方法比较暴力

主要是评论区那句长度一定小于2a+b提醒了我

要确定叠加的次数那就要有个上限

什么时候不叠加了呢？

就是叠加后的字符串长度小于2a+b并且包含b

这样就能确保叠加后的字符串有且仅有一个b子串

一次循环下来就可以得出答案了

当然我这样做的效率很低

看了题解才发现大佬们都用的kmp

kmp对现在的我来说属实学不会

寄了寄了