Count The Repetitions

Count The Repetitions

定义\(conn(s,n)\)为字符串s重复n次形成的新字符串,定义字符串a能被字符串b生成,当且仅当a是b的子串,现在给出s1,n1,s2,n2,求最大的m使\(conn(conn(s2,n2),m)\)能被\(conn(s1,n1)\)生成,\(s_1\) 和 \(s_2\) 长度不超过100,\(n_1\) 和 \(n_2\) 不大于 \(10^6\)。

首先\(conn(conn(s2,n2),m)=conn(s2,n2\times m)\),于是可以令\(m'=n2\times m\),现在只要求出最大的m即可。

注意到字符串为循环节,循环节,模数是倍增的大展身手之处,于是我们可以设\(f[i][j]\)表示s1中的第i个位置开始至少要多少个字符,形成\(2^j\)个s2,当j=0,可以\(n^2\)枚举,注意判断无解的情况,而且如果一个地方有解的话,每个地方都会有数值。

因此不难有

\(f[i][j]=f[i][j-1]+f[i+f[i][j-1]][j-1]\)

维护好了倍增数组,接下来二进制拆分考虑问题,s1存在范围,故从大的次幂到小枚举,并保证不超过\(s1.size()\times n1\)的前提下,尽可能让m大,输出\(n/n2\)即可。

参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
using namespace std;
string s1,s2;
int len1,len2;
ll dp[150][28];
il void work(int,int);
int main(){
    int n1,n2;
    while(cin>>s2>>n2>>s1>>n1)work(n1,n2);
    return 0;
}
il void work(int n1,int n2){
    memset(dp,0,sizeof(dp));
    int li((ll)n1*s1.size()),m(0);
    for(int i(0),j,k,tot;i<s1.size();++i)
        for(j=0,k=i;j<s2.size();++j){tot=0;
            while(s1[k]!=s2[j]&&tot<=s1.size())(++k)%=s1.size(),++tot;
            if(tot>s1.size())return (void)(puts("0"));
            dp[i][0]+=tot+1,(++k)%=s1.size();
        }
    for(int j(1),i;j<28;++j)
        for(i=0;i<s1.size();++i)
            dp[i][j]=dp[i][j-1]+dp[(i+dp[i][j-1])%s1.size()][j-1];
    for(int i(27),j(0);i>=0;--i)
        if(dp[j][i]<=li)
            li-=dp[j][i],m+=1<<i,(j+=dp[j][i])%=s1.size();
    printf("%d\n",m/n2);
}
上一篇:BSOJ1477 -- 【算法竞赛】Count The Repetitions


下一篇:爬虫爬取百度贴吧(python)