LeetCode 466. 统计重复个数，循环字符串匹配优化

本文主要是介绍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. 统计重复个数，循环字符串匹配优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---