leetcode 466. 统计重复个数（寻找循环节）

由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，[“abc”,3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，“abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

示例：

输入：
s1 =“acb”,n1 = 4
s2 =“ab”,n2 = 2

返回：
2

思路就是寻找s1中的循环节，因为直接把每一个s1串遍历完时间复杂度太高，不现实。

具体思路就是记录每次遍历完一遍s1串指针停留在s2串的哪个位置，如果以前某一次遍历停留的位置和当前位置一样，那么就说明出现了循环节，为了直观表达，用一张leetcode题解上的图，很清晰。

说起来很简单，但是具体实现起来比较复杂，最麻烦的一点在于循环节开始的地方并不是s2刚开始的地方，比如上图中循环节是bdadc并不是adcbd。

但是只要稍微转化一下，因为一开始进入循环节之前就有adc三位了，那么遍历完所有的循环节之后，肯定还会剩余adc三位，所以可以把不是从s2的第一位开始看做从s2的第一位开始，想通了这一点就很简单了，具体见代码。

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len_1 = s1.length();
        int len_2 = s2.length();
        int last[] = new int [121];//上次指针停在s2串i位时是遍历完last[i]个s1串
        int tot[] = new int [1210000];//遍历完第i次s1串记录总共出现了tot[i]个s2串
        for(int i=0;i<=100;i++)
            last[i] = -1;
        last[0] = 0;
        tot[0] = 0;
        int cnt = 1;//记录遍历了几次s1串
        int dir = 0;//记录遍历到s2串哪个位置
        int sum = 0;//记录s2串总共出现了多少次
        boolean ok = false;//记录是否找到循环节
        while(cnt<=n1)
        {
            for(int i=0;i<len_1;i++)
            {
                if(s1.charAt(i)==s2.charAt(dir))
                {
                    dir++;
                    if(dir>=len_2)
                    {
                        sum++;
                        dir = 0;
                    }
                }
            }
            tot[cnt] = sum;
            if(ok)//找到循环节之后剩余的s1串很少了，直接遍历即可
            {
                cnt++;
                continue;
            }
            if(last[dir]==-1)//当前s2停留的位置此前未出现过
            {
                last[dir] = cnt;
                cnt++;
            }
            else
            {
                int loop = cnt - last[dir];//距离上次停留到s2串当前位置过了多少个s1串
                int gap = tot[cnt] - tot[last[dir]];//离上次停留到s2串当前位置又多出现了几次s2串
                sum = sum + ((n1-cnt)/loop*gap);//直接把每一个循环节出现的s2串都计算上
                cnt = n1 - ((n1-cnt)%loop) + 1;//除去所有遍历过的循环节直接跳到最后几个不在循环节内的s1串
                ok = true;
            }
        }
        return sum/n2;
    }
}