《算法竞赛进阶指南》0x57倍增优化DP AcWing294计算重复

题目链接：https://www.acwing.com/problem/content/description/296/

定义conn(s,n)表示由n个s拼接的字符串，问最大的m满足conn(s2,m)能通过conn(s1,n)生成，生成就是去掉一些位置的字符之后能够变成s1。

通过倍增的思想，可以算每个位置i起2的j次方个s2需要多少长度能够拼接，最终将可以拼成的数量进行二进制拆分，位置进行累加，保证位置不超过s1*n的情况下找到最大的包含s2的数量。

这里注意需要枚举起点，因为每个位置起的拼成一个s2的最短长度是不同的，所以找包含s2最多的情况需要对每个起点进行枚举。

代码：

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
const int N = 110, M=32;
typedef long long ll;
ll f[N][M];//从i位置开始匹配1<<j个s2
string s1,s2; 
ll n1,n2;
int main(){
    while(cin>>s2>>n2>>s1>>n1){
        ll size1=s1.length();
        ll size2=s2.length();
        
        bool fail=false;
        for(int i=0;i<size1;i++){
            f[i][0]=0;
            int pos=i;
            for(int j=0;j<size2;j++){
                int cnt=0;
                while(s1[pos]!=s2[j]){
                    pos=(pos+1)%size1;
                    cnt++;
                    if(cnt>=size1){ 
                        fail=true;
                        break;
                    }
                }
                if(fail)break;
                f[i][0]+=cnt+1;//匹配每一个字符用的长度 
                pos=(pos+1)%size1;//下一个匹配的位置 
            }
            if(fail)break;
        }
        
        if(fail){
            cout<<0<<endl;
            continue;
        }
        
        for(int j=1;j<=30;j++){
            for(int i=0;i<size1;i++){
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%size1][j-1];
            }
        }
        
        ll ans=0;
        for(int i=0;i<size1;i++){
            ll p=i,x=0;
            for(int j=30;j>=0;j--){
                if(p+f[p%size1][j] <= n1*size1){//长度没有超过 
                    x+=1<<j;
                    p+=f[p%size1][j];                    
                }
            }
            ans=max(ans,x);
        }
        
        cout<<ans/n2<<endl;
    }
}

《算法竞赛进阶指南》0x57倍增优化DP AcWing294计算重复

相关推荐