题解：P10976 统计重复个数

· · 题解

题解：P10976 统计重复个数

题目传送门

题意解读

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

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

大致思路

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

首先，原文中说：

如果可以从 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 构造的。即：

[[s_2,n_2],m] = [s_2,n_2 \times m]

那么原题就变为了：请你找出一个最大整数 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;//好习惯
}