LEETCODE算法:466. Count The Repetitions

题目

Define S = [s,n] as the string S which consists of n connected strings s. For example, ["abc", 3] ="abcabcabc".

On the other hand, we define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1. For example, “abc” can be obtained from “abdbec” based on our definition, but it can not be obtained from “acbbe”.

You are given two non-empty strings s1 and s2 (each at most 100 characters long) and two integers 0 ≤ n1 ≤ 106 and 1 ≤ n2 ≤ 106. Now consider the strings S1 and S2, where S1=[s1,n1] and S2=[s2,n2]. Find the maximum integer M such that [S2,M] can be obtained from S1.

Example:

Input: s1="acb", n1=4 s2="ab", n2=2

Return: 2

题解

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        if(n1==0) return 0;
        int s1cnt=0,s2cnt=0,index=0;
        int ans=0,last=0;
        map<int,pair<int,int>> recall;
        while(1)
        {
            s1cnt++;//遍历新的一个s1字符串
            for(auto t:s1)
            {
                if(t==s2[index])
                {
                    index++;
                    if(index==s2.length())
                    {
                        s2cnt++;
                        index=0;
                    }
                }

            }
            if(s1cnt==n1)
            {//s1不够找循环节了
                return s2cnt/n2;
            }
            if(recall.find(index)!=recall.end())
            {//找到index，循环节已经找到，提出之前放进的数据
                auto [s1pre,s2pre]=recall[index];
                ans=(n1-s1pre)/(s1cnt-s1pre)*(s2cnt-s2pre)+ s2pre;
                last=(n1-s1pre)%(s1cnt-s1pre);
                break;
            }else{
                recall[index]={s1cnt,s2cnt};
            }
        }
        for(int i=0;i<last;i++)
        {
            for(auto t:s1)
            {
                if(t==s2[index])
                {
                    index++;
                    if(index==s2.length()) 
                    {
                        ans++;
                        index=0;
                    }
                }
            }
        }
        return ans/n2;
    }
};

说明

• 整体思路是在n1个s1中找s2，要得到x个s1中有y个s2，循环节开始前有z个s1。
• 方法其实就是暴力搜索，不过找到循环节立即结束，最后剩下的几个s1再使用同样的暴力搜索

官方题解

https://leetcode-cn.com/problems/count-the-repetitions/solution/tong-ji-zhong-fu-ge-shu-by-leetcode-solution/