LeetCode 466. 统计重复个数（循环节）

示例：
输入：
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回：
2

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
    	if(n1*s1.size() < n2*s2.size())
    		return 0;
    	int len1 = s1.size(), len2 = s2.size(), cnt1 = 0, cnt2 = 0, i, j=0;
    	unordered_map<int,pair<int,int>> m;//j, cnt1, cnt2
    	while(cnt1 < n1)
    	{
    		for(i = 0; i < len1; ++i)
    		{
    			if(s1[i]==s2[j])
    				j++;
    			if(j==len2)//循环单个s2
    				j=0,cnt2++;//完整个数
    		}
    		cnt1++;//s1的个数
    		if(!m.count(j))//j停在什么位置
    			m[j] = make_pair(cnt1, cnt2);//记录停在j位置时的cnt
    		else
    		{	//再次找到同一个 j 时，产生循环节了
    			int lastcnt1 = m[j].first;//上次的cnt
    			int lastcnt2 = m[j].second;
    			int gap1 = cnt1-lastcnt1;//做差，中间间隔有多少个
    			int gap2 = cnt2-lastcnt2;
    			int num = (n1-cnt1)/gap1;//剩余的够多少个循环
    			cnt1 += num*gap1;//cnt1 直接+到接近结束
    			cnt2 += num*gap2;
    		}
    	}
    	return cnt2/n2;//n1个s1可以找到cnt2个s2，可以找到cnt2/n2 个(n2*s2)
    }
};