自动搬运

查看原文

来自洛谷，原作者为

	yiLIUyi 不屈的江油人民终会迎来光明|看主页：F12删除“display: none;”|互关条件luogu.com.cn/paste/x54efpmj 满足可私信|准九年级|山东|可以加微信/qq聊天

搬运于2025-08-24 23:03:06，当前版本为作者最后更新于2025-02-23 10:04:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P10976 统计重复个数

题目传送门

题意解读

题目中的输入格式有误，应该为：

• 第一行输入字符串 $s_2$ 和整数 $n_2$；
• 第二行输入字符串 $s_1$ 和整数 $n_1$。

其他内容题目已经讲的很明确了。这里不再多说。

大致思路

感觉其他人的方法都过于复杂（因为我是个蒟蒻）。所以我讲一种最简单的暴力解法。

首先，原文中说：

如果可以从 $s_2$ 中删除某些字符使其变为 $s_1$，则称字符串 $s_1$ 可以从字符串 $s_2$ 获得。

例如，根据定义，$s1 = \tt{abc}$ 可以从 $s2 = \tt{ab\red{dbe}c}$ 获得，仅需要删除红色标识的字符。

于是，如果想要使得字符串 $s_2$ 可以从字符串 $s_1$ 获得，就要在 $s_1$ 中找到按顺序排列 $s_2$ 的全部字符。也就是说 $s_2$ 是 $s_1$ 的一部分，但注意并不是子串，因为 $s_2$ 在 $s_1$ 中并不一定连续。

我们不妨利用一个循环，设定一个 $s_1$ 的下标 $i$，一个 $s_2$ 的下标 $j$，然后对 $s_1$ 进行遍历，如果 ${s_1}_i$ 与 ${s_2}_j$ 相同，那么 $i$ 和 $j$ 都增加，比较下一位；否则 $i$ 增加，比较下一位。这样，如果 $j$ 与 $s_2$ 的长度相等，则说明 $s_2$ 的所有字符都被找到，那么 $s_2$ 就可以从 $s_1$ 获得；反之，如果 $i$ 与 $s_1$ 的长度相等，则说明 $s_1$ 的所有字符都遍历过一遍，循环结束。

再进一步，根据题意，$s_1$ 中可能有多个 $s_2$。需要一个变量 $ans$ 来记录 $s_2$出现的次数。这时，如果 $j$ 与 $s_2$ 的长度相等，则说明 $s_2$ 的所有字符都被找到，那么 $ans$ 就增加，直到 $i$ 与 $s_1$ 的长度相等，循环终止。

ll num1=str1.size(),num2=str2.size();//分别代表两个字符串的长度
for(ll i=0,j=0;i<num1;i++){//注意：这里下表从0开始！
	if(str1[i]==str2[j]){//如果两位相等
		if(j==num2-1){//如果位数达到（下表从0开始，所以到 num2-1就结束了）
			ans++;//统计个数增加
			j=0;//回到下标开头，寻找下一轮
		}else j++;//否则继续找下一位
	}//如果两位不相等，则不进行操作，i增加，比较下一位
}

其次，我们可以知道，最终的 $str$ 是由 $m$ 个 $str_2$ 构造的，而 $str_2$ 本身又是由 $n_2$ 个 $s_2$ 构造而来的。所以就可以得到 $str$ 是由 $m \times n_2$ 个 $s_2$ 构造的。即：

那么原题就变为了：请你找出一个最大整数 $m$，以满足 $str = [s2,n2 \times m]$ 可以从 $str_1$ 获得。

所以，对于这道题，我们用刚才的代码先在 $str_1$ 中寻找 $s_2$，此时 $ans$ 等于 $s_2$ 的个数，也就是 $n_2 \times m$。对它除以 $n_2$，则 $\lfloor \frac{ans}{n_2} \rfloor$ 就是 $m$。

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n1,n2,ans;//变量名如题
string s1,s2,str1,str2;
int main(){
	while(cin>>s2>>n2>>s1>>n1){
		str1=str2="";//清空
		for(ll i=0;i<n1;i++)
			str1+=s1;//构建str1
		str2=s2;
		ll num1=str1.size(),num2=str2.size();
		for(ll i=0,j=0;i<num1;i++){
			if(str1[i]==str2[j]){
				if(j+1==num2){
					ans++;
					j=0;
				}else j++;
			}
		}cout<<ans/n2<<endl;//输出答案
		ans=0;//清空
	}return 0;//好习惯
}