codefoces 1110 H：Modest Substrings（AC自动机，动态规划）

You are given two integers l and r.

Let’s call an integer x modest, if l≤x≤r.

Find a string of length n, consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one.

If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.

Input
The first line contains one integer l (1≤l≤10^800).

The second line contains one integer r (l≤r≤10^800).

The third line contains one integer n (1≤n≤2000).

Output
In the first line, print the maximum possible number of modest substrings.

In the second line, print a string of length n having exactly that number of modest substrings.

If there are multiple such strings, print the lexicographically smallest of them.

Examples
input
1
10
3
output
3
101
input
1
11
3
output
5
111
input
12345
12346
6
output
1
012345
Note
In the first example, string «101» has modest substrings «1», «10», «1».

In the second example, string «111» has modest substrings «1» (3 times) and «11» (2 times).

---

考虑一个数位 $dp$ 的过程，一个数确定在 $l-r$ 之间肯定是从某一位开始的

很容易发现只有两种情况：
$x$ 和 $l,r$ 前 $k$ 位完全一样且 $x_{k+1}\in (l_{k+1},r_{k+1})$
$x$ 和 $l(r)$ 前 $k$ 位完全一样但和 $r(l)$ 有不一样且 $x_{k+1}\in (l_{k+1},9)((0,r_{k+1}))$
一个暴力的做法就是把 $[l,r]$ 之间所有的数插到 $AC$ 自动机上并在每一个转移的时候更新一下答案
然后直接在 $AC$ 自动机上 $dp$ 就好了

考虑优化显然有些位是没用的，我们只在意他是时候和 $l,r$ 出现不同的
于是我们只要把 $l,r$ 插到 $AC$ 自动机上，并维护一下每个点转移出去对答案的影响再 $dp$

注意这个东西是可以沿着 $fail$ 指针传递的，细节可看代码

输出方案直接沿着 $dp$ 数组贪心就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define ll long long
#define son(x,i) ( !ch[x][i] ? ch[x][i] = ++tot : ch[x][i] )
void gi(int &sum){
    sum = 0;char c = getchar();bool flag = true;
    while(c < '0' || c > '9') {if(c == '-') flag = false;c = getchar();}
    while(c >= '0' && c <= '9') sum = sum * 10 + c - 48,c = getchar();
    if(!flag) sum = -sum;
}
const int INF = 2e9;
char L[810],R[810];
int n,m,k,tot;
int ch[16100][10],fail[16100],sum[16100][2010];
int f[2010][16100];
bool vis[2010][16100];
queue<int>q;
inline void chmax(int &x,int y){if(x<y) x = y;}
void build_up(){
	n = strlen(L+1),m = strlen(R+1);int u = 1,v = 1;
	if(n == m){
		rep(i,1,n)
			if(u == v){
				rep(j,L[i]-'0'+1,R[i]-'0'-1) 
				    sum[son(u,j)][n-i]++;
				u = son(u,L[i]-'0'); v = son(v,R[i]-'0');
			}
			else {
				rep(j,L[i]-'0'+1,9)
				    sum[son(u,j)][n-i]++;
				rep(j,(i==1?1:0),R[i]-'0'-1)
				    sum[son(v,j)][n-i]++;
			    u = son(u,L[i]-'0'); v = son(v,R[i]-'0');
			}
		sum[u][0]++;sum[v][0] += u!=v;
	}
	else {
		rep(i,1,n){
			rep(j,L[i]-'0'+1,9)
			    sum[son(u,j)][n-i]++;
			u = son(u,L[i]-'0');
		}
		rep(i,1,m){
			rep(j,(i==1?1:0),R[i]-'0'-1)
			    sum[son(v,j)][m-i]++;
			v = son(v,R[i]-'0');
		}
		rep(k,n+1,m-1)
		    rep(j,1,9)
		        sum[son(1,j)][k-1]++;
		sum[u][0]++; sum[v][0]++;
	}
}
void find_fail(){
	rep(i,0,9) if(!ch[1][i]) ch[1][i] = 1;
	else {
		fail[ch[1][i]] = 1;
		q.push(ch[1][i]);
	}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		rep(i,0,m) sum[x][i] += sum[fail[x]][i];
		rep(i,0,9)
		    if(!ch[x][i]) ch[x][i] = ch[fail[x]][i];
		    else fail[ch[x][i]] = ch[fail[x]][i],q.push(ch[x][i]);
	}
	rep(i,1,tot) rep(j,1,k) sum[i][j] += sum[i][j-1];
}
void Dp(){
	rep(i,0,k) rep(j,1,tot) f[i][j] = -INF;
	f[0][1] = 0;
	rep(i,0,k-1) rep(j,1,tot)
	    if(f[i][j] >= 0){
		    rep(t,0,9)
	        	chmax(f[i+1][ch[j][t]],f[i][j] + sum[ch[j][t]][k-i-1]);
	    }
	int ans = 0,now = 1;
	rep(i,1,tot) ans = max(ans,f[k][i]);
	printf("%d\n",ans);
	rep(i,1,tot) vis[k][i] = f[k][i] == ans;
	repp(i,k-1,0)
	    rep(j,1,tot) if(f[i][j] >= 0)
	        rep(t,0,9){
	            vis[i][j] |= vis[i+1][ch[j][t]] && 
	            f[i+1][ch[j][t]] == f[i][j] + sum[ch[j][t]][k-i-1];
	            if(vis[i][j]) break;
			}
	rep(i,1,k) rep(j,0,9) if(vis[i][ch[now][j]] && f[i][ch[now][j]] == f[i-1][now] + sum[ch[now][j]][k-i]){
		putchar(j + '0');
		now =  ch[now][j];
		break;
	}
}
int main(){
	scanf("%s",L+1); scanf("%s",R+1); gi(k);
	tot = 1; build_up();
	find_fail();
	Dp();
    return 0;
}