题解：P10976 统计重复个数

· · 题解

大家写的怎么都是同一种做法？我来给出一个另类的倍增方法。

以下所有的字符串下标均从 0 开始。

第一步是转化题意，[[s2,n2],m]=[s2,n2 \times m]，找最大的 m 就是找最大的 t 使得 [s2,t] 能由 [s1,n_1] 获得，m 就是 \lfloor {t \over n_2} \rfloor。

我们以 s_2 为基准，设 nxt_i 表示从 s_2 的第 i 个字符开始，在 s_1 中匹配，匹配完整个串后匹配到了第几位，val_i 表示在这个过程中匹配出了几个 s_2。注意，第一段不完整的代表前面有一段已经匹配好的，所以应当计入答案。

直接说可能不是很好理解，我来给个例子。

设 s_1=\texttt{cycycycyc}，s_2=\texttt{cyc}。

nxt_0=1$，$val_0=2$，具体分配方式如下。$\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{c} nxt_1=1$，$val_1=2$，具体分配方式如下。$\color{black}\texttt{c}\color{red}\texttt{yc}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{c} nxt_2=0$，$val_2=3$，具体分配方式如下。$\color{red}\texttt{c}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{cyc}

这样就可以快速的将一个 s_1 与 s_2 匹配了，只需要匹配 n_1 次就能得出答案。

但是它还是不够快，因此考虑倍增优化。套路的，设 dp_{i,j} 表示从 s_2 的第 j 个字符开始，在 s_1 中匹配完 2^i 个串后匹配到了第几位，cur_{i,j} 表示在这个过程中匹配出了几个完整的 s_2。

转移方程就是把它劈成两半分别计算。

dp_{i,j}=dp_{i-1,(dp_{i-1,j})},cur_{i,j}=cur_{i-1,j}+cur_{i-1,(dp_{i-1,j})}

然后对 n_1 进行二进制拆分，对每个二进制位进行计算。

讲的可能有点朦胧，可以看看代码。

// Problem: P10976 统计重复个数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10976
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Author: Binah_cyc

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=105;
int n1,n2;
string s1,s2;
int nxt[N],val[N];
int dp[25][N],cur[25][N];
main()
{
    cin.tie(0)->sync_with_stdio(false);
    while(cin>>s2>>n2>>s1>>n1)
    {
        for(int i=0;i<s2.length();i++)
        {
            int it=i;
            for(int j=0;j<s1.length();j++)//匹配字符串
            {
                if(s1[j]==s2[it])
                {
                    it++;
                    if(it==s2.length()) val[i]++,it=0;//匹配了一整个字符串
                }
            }
            nxt[i]=it;
        }
        for(int i=0;i<s2.length();i++)
            dp[0][i]=nxt[i],cur[0][i]=val[i];
        for(int i=1;i<=20;i++)
        {
            for(int j=0;j<s2.length();j++)
            {
                dp[i][j]=dp[i-1][dp[i-1][j]],cur[i][j]=cur[i-1][j]+cur[i-1][dp[i-1][j]];//正常倍增
            }
        }
        int now=0,num=0;
        for(int i=20;i>=0;i--)//从高位到低位考虑
        {
            if((1<<i)<=n1)//n1的这一位有值
            {
                n1-=(1<<i),num+=cur[i][now],now=dp[i][now];
            }
        }
        cout<<num/n2<<'\n';
        for(int i=0;i<s2.length();i++) val[i]=nxt[i]=0;//多测要清空
    }
    return 0;
}