本文主要是介绍LeetCode 466. 统计重复个数，循环字符串匹配优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
1、题目描述
定义
str = [s, n]表示str由n个字符串s连接构成。
- 例如，
str == ["abc", 3] =="abcabcabc"。如果可以从
s2中删除某些字符使其变为s1，则称字符串s1可以从字符串s2获得。
- 例如，根据定义，
s1 = "abc"可以从s2 = "abdbec"获得，仅需要删除加粗且用斜体标识的字符。现在给你两个字符串
s1和s2和两个整数n1和n2。由此构造得到两个字符串，其中str1 = [s1, n1]、str2 = [s2, n2]。请你找出一个最大整数
m，以满足str = [str2, m]可以从str1获得。
2、接口描述
class Solution {
public:int getMaxRepetitions(string s1, int n1, string s2, int n2) {}
};3、原题链接
466. 统计重复个数
二、解题报告
1、思路分析
官方给出的解法是循环节解法，笔者采用了类似KMP优化字符串匹配的思想，不难想到我们只要计算出n1个s1中匹配的s2的数量然后除以n2就是答案，那么我们无非就是在s1 * n1这个字符串上进行了一次字符串匹配，我们暴力的求解，即从第0个字符一直到len1 * n1个字符进行和s2的匹配，记录s2的数目则有如下暴力代码：
class Solution {
public:Solution(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);}int getMaxRepetitions(string s1, int n1, string s2, int n2) {int len1 = s1.size() , len2 = s2.size() , p2 = 0 , cnt = 0;for(int i = 0 ; i < n1 ; i++)for(int j = 0 ; j < len1 ; j++)if(s1[j] == s2[p2]){p2++;if(p2 == len2)p2 = 0 , cnt ++;}return cnt / n2;}
};n1可以达到1e6量级，len1可以达到100量级，那么总体就是1e8量级，不出意外，49个样例全部通过但是卡常，所以还是没过。
但这说明只要对暴力解法进行小优化就可以通过本题。由于在一个循环字符串中寻找另一个字符串的数目，这显然有许多的冗余匹配，那么我们不妨像kmp那样，开一个数组nxt[]，nxt[i]存储从s2下标i开始和单个s1能够匹配的字符串数目（这里s2是循环的，但是统计的是和单个s1匹配的字符数目），nxt的求解可以暴力求解，由于len1，len2不超过100，所以整体预处理不超过1e4
有了nxt后，我们再在n1 * s1 上进行匹配就可以优化为O(n1)了，为什么呢？
两个字符串从0开始匹配，第一个s1匹配结束，s2下标从0变为(nxt[0] + 0)%len2，再跟第二个s1匹配，s2下标又变为 ((0 + nxt[0]) % len1 + nxt[(0 + nxt[0]) % len1]) % len1……
直接看代码会明了很多
2、复杂度
时间复杂度： O(n1) 空间复杂度：O(L)
3、代码详解
相比于循环节的方法，该方法的代码要简洁很多，当然该方法也可以进一步优化为循环节方法，如果让你将该方法进一步优化，那么阁下又该如何应对呢？
class Solution {
public:
int nxt[101] , len1 , len2 , sum;int getMaxRepetitions(string s1, int n1, string s2, int n2) {memset(nxt , 0 , sizeof(nxt));len1 = s1.size() , len2 = s2.size() , sum = 0;for(int i = 0 ; i < len2 ; i++)for(int j = i , k = 0 ; k < len1 ; k++)if(s2[j] == s1[k])nxt[i]++ , j = (j + 1) % len2;for(int i = 0 ,j = 0 ; i < n1 ; i++)sum += nxt[j] , j = (j + nxt[j]) % len2;return sum / (len2 * n2);}
};这篇关于LeetCode 466. 统计重复个数，循环字符串匹配优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
