leetcode 686. Repeated String Match 字符串迭代找子串

た入场券 2022-06-03 08:28 148阅读 0赞

Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.

For example, with A = “abcd” and B = “cdabcdab”.

Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times (“abcdabcd”).

Note:  
The length of A and B will be between 1 and 10000.

直接使用C++的find函数做查找即可，当A的长度小于B的时候，我们可以先进行重复A，直到A的长度大于等于B，并且累计次数cnt。那么此时我们用find来找，看B是否存在A中，如果存在直接返回cnt。如果不存在，我们再加上一个A，再来找，这样可以处理这种情况A=”abc”, B=”cab”，如果此时还找不到，说明无法匹配，返回-1，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int repeatedStringMatch(string a, string b)
        {
            int count = 1;
            string aa = a;
            while (aa.length() < b.length())
            {
                count++;
                aa += a;
            }
    
            if (aa.find(b) != aa.npos)
                return count;
            else
            {
                aa += a;
                if (aa.find(b) != aa.npos)
                    return count + 1;
                else
                    return -1;
            }
        }
    };