题解：CF1110H Modest Substrings

· · 题解

压缩 DFA 的好题。但是还挺难写的。代码参考了某篇题解。

首先我们考虑暴力，把 [l,r] 的所有数插入 AC 自动机里边去，转化成多模式串匹配问题（模式串为 [l,r] 所有整数的十进制表示）。设 f_{len,node} 表示填完前 len 位，目前在 node 节点，合法子串数最多是多少。

然后另设辅助转移数组 g_{node} 表示根到 node 的路径组成的串 T 上，有多少个后缀（可以包含本身）为模式串。采用后缀的原因是，我们要记录新加的那个字符的贡献。

这个其实就是【模版】AC自动机。等价于 node 在 fail 树上的所有祖先中，是模式串结尾的节点个数。这个也很好理解，直接用 fail 的定义就行（fail_{node} 指向的节点 x 代表一个最长的模式串的前缀，使其是 node 所代表的串的后缀）。求这个东西直接递推就行。

考虑优化。朴素 DP 会在 [l,r] 中插入所有数字，状态量极大。观察到很多子树在本质上是「满 10 叉树」，可以被整体压缩。

我们类比数位 DP 的思想：当构造数时，只要前面的部分已经“脱离上界限制”，那么后续各位都可以自由取值。这类情况可以用一对参数 (d,m) 来描述：

这样一来，我们就可以只在压缩后的 DFA（相当于“数位状态自动机”）上进行转移，而不用显式展开所有数字。

我们考虑在压缩之后，通过计算“一定可以的贡献”来拼出答案。注意这里 f 的转移不变。

我们先说怎么做，然后说为什么。

在压缩后的自动机上，我们需要考虑「当前节点后续还能接 m 个自由位」时的最大匹配贡献。

对于每个节点 node，若其后能接续 m 个自由位，则「一定会产生贡献」的部分，就是所有满足条件的 (s,l) 组合：

由于无论后面具体走的 step \le m 步怎么填，这些模式串都会出现，因此我们可以一次性累加这些确定的贡献：

那这个为啥是对的呢？我们可以将所有自由位上可能出现的情况分为两类讨论：

我们可以可考虑用 g_{node,len} 表示这个贡献，转移类似原来辅助数组的转移，不过是加了一维。

但如何算初始时有哪些形如 (d,m) 的对也是一个问题。这个直接用 (d,m) 的定义，枚举长度（等于 |l|，在 [|l|+1,|r|-1]，等于 |r|），和在哪一位分离，分讨即可。具体地，对当前走到的节点 x，我们把 x 的可以创造分离的儿子创建形如 (d,m) 的对，在 [|l|+1,|r|-1] 就直接从根创建即可。注意分讨 |l|=|r| 的情况。

转移时，我们尝试所有数字字符 c \in [0,9]，并利用自动机转移函数 son_{node,c} 与自由位贡献 g_{next,tail} 更新状态：

f_{i,next} = \max(f_{i,next}, f_{i-1,node} + g_{next,tail})

其中 tail = \min(n-i, LIM)，即剩余自由位上限，next 为自动机接收 c 后会跳到哪里。

最终答案为所有 f_{n,*} 中的最大值。 为了得到字典序最小的最优解，直接从 f_{n,*} 的最优解开始倒退，看他们能从哪里来。无需显式减出 dag，从 f_{0,0} 开始，选能到最优解且字典序最小的解即可。

#include<bits/stdc++.h>
#define _for(i,x,y) for(int i=x;i<=y;++i)
#define _forp(i,x,y,z) for(int i=x;i<=y;i+=z)
#define _rep(i,x,y) for(int i=x;i<y;++i)
using namespace std;
const int N=2005,Node=17005,M=805,V=9;      
string L,R; 
int lenl,lenr,n;
int f[N][Node];
int g[Node][N];
int son[Node][V+5];
int fail[Node];
int node;
bool vis[N][Node];
int ans=0;
int LIM;

int T(char c){
    return (int)(c-'0');
}

void CLEAR(int rt,int num){
    son[rt][num]=0;
}

void upd_son(int root,int l,int r,int len){
    if(l>r) return ;
    if(len<0) return;
    _for(i,l,r){ 
        if(!son[root][i]) son[root][i]=++node;
        g[son[root][i]][len]++;
    }
}

void first_build_G(){
    int pl=0,pr=0;
    if(lenl==lenr){
        _rep(i,0,lenl){
            if(pl==pr){
                //前缀相等
                upd_son(pl,T(L[i])+1,T(R[i])-1,lenl-i-1);

                if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
                if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
                pl=son[pl][T(L[i])];
                pr=son[pr][T(R[i])];
            }else{
                upd_son(pl,T(L[i])+1,9,lenl-i-1);
                upd_son(pr,0,T(R[i])-1,lenl-i-1);

                if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
                if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
                pl=son[pl][T(L[i])];
                pr=son[pr][T(R[i])];
            }   
        }
        if(L!=R){
            g[pl][0]++;
            g[pr][0]++;
            // cout<<'!'; 
        }else g[pl][0]++;
        CLEAR(0,0);
    }else{
        //在 (|L|,|R|)
        _for(len,lenl+1,lenr-1){
            upd_son(0,1,9,len-1);
        }
        //|L|
        _rep(i,0,lenl){
            upd_son(pl,T(L[i])+1,9,lenl-i-1);

            if(!son[pl][T(L[i])]) son[pl][T(L[i])]=++node;
            pl=son[pl][T(L[i])];
        }
        //|R|
        _rep(i,0,lenr){
            upd_son(pr,0,T(R[i])-1,lenr-i-1);

            if(!son[pr][T(R[i])]) son[pr][T(R[i])]=++node;
            pr=son[pr][T(R[i])];
        }
        g[pl][0]++;
        g[pr][0]++;
        CLEAR(0,0);
    }

    queue<int> q;
    _for(i,1,V) if(son[0][i]) q.push(son[0][i]),fail[son[0][i]]=0;

    while(!q.empty()){
        int top=q.front();
        q.pop();
        _for(i,0,V){
            if(son[top][i]){
                q.push(son[top][i]);
                fail[son[top][i]] = son[fail[top]][i];
                _for(j,0,LIM) g[son[top][i]][j]+=g[fail[son[top][i]]][j];
            }else{
                son[top][i]=son[fail[top]][i];
            }
        }
    }
}

void build_final_f(){
    // _for(i,0,node){
        // _for(j,1,n){
            // cout<<g[i][j]<<' ';
        // }
        // cout<<'\n';
    // }
    _for(i,0,node) _for(j,1,LIM)
        g[i][j]+=g[i][j-1];

    _for(i,0,n) _for(j,0,node) f[i][j]=-0x3f3f3f3f;

    f[0][0]=0;
    _for(i,1,n){
        _for(j,0,node){
            if(f[i-1][j]>=0){
                _for(c,0,9){
                    int nxt=son[j][c];
                    // cout<<i<<':'<<nxt<<'\n';
                    // cout<<g[nxt][n-i]<<'\n';
                    int tail=min(n-i,LIM);  
                    f[i][nxt]=max(f[i-1][j]+g[nxt][tail],f[i][nxt]);
                    ans=max(ans,f[i][nxt]);
                }
            }   
        }
    }
    cout<<ans<<'\n';
}

void solve(){
    memset(son,0,sizeof(son));
    memset(fail,0,sizeof(fail));
    memset(g,0,sizeof(g));
    node=0;ans=0;

    cin>>L>>R>>n;
    lenl=L.size();
    lenr=R.size();

    int maxTail = (lenl==lenr ? lenl-1 : lenr-1);
    LIM = min(n, maxTail);

    first_build_G();//不算前缀和，只算单点
    build_final_f();

    _for(i,n,n){
        _for(j,0,node){
            if(f[i][j]==ans){
                vis[i][j]=1; 
            }
        }
    }
    for(int i=n-1;i>=0;--i){
        _for(j,0,node){
            if(f[i][j]>=0){
                _for(c,0,9){
                    int nxt=son[j][c];
                    int tail=min(n-i-1,LIM);
                    if(f[i][j]+g[nxt][tail]==f[i+1][nxt]&&vis[i+1][nxt]){
                        vis[i][j]=1; 
                    }
                }
            }
        }
    }
    int nw=0;
    _for(i,0,n-1){
        _for(c,0,9){
            int nxt=son[nw][c];
            int tail=min(n-i-1,LIM);
            if(f[i][nw]+g[nxt][tail]==f[i+1][nxt]&&vis[i+1][nxt]){
                nw=nxt;
                cout<<(char)('0'+c);
                break;
            }
        }
    }
}
signed main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}