Modest Substrings
Contest: Codeforces Global Round 1
Difficulty rating: 3500
Tags: dp, strings

You are given two integers $$$l$$$ and $$$r$$$.

Let's call an integer $$$x$$$ modest, if $$$l \le x \le 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 format:
The first line contains one integer $$$l$$$ ($$$1 \le l \le 10^{800}$$$).

The second line contains one integer $$$r$$$ ($$$l \le r \le 10^{800}$$$).

The third line contains one integer $$$n$$$ ($$$1 \le n \le 2\,000$$$).

Output format:
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.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

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).

Example input:
1
10
3

Example output:
3
101

Example input:
1
11
3

Example output:
5
111

Editorial:
Set of modest numbers could be represented by set of size approximately $$$(|l| + |r|) \cdot 10$$$ of regular expressions of form $$$d_0 d_1 d_2 \dots d_{k - 1} [0-9]\{e\}$$$, where $$$|l|$$$ and $$$|r|$$$ are lengths of numbers $$$l$$$ and $$$r$$$ correspondingly, and $$$d_i$$$ are digits. Set of regular expressions can be build in the following way. Consider prefix of $$$l$$$ of length $$$x$$$. Then for every $$$q > l_x$$$ let's make the following expression: $$$l_0 l_1 l_2 \dots l_{x - 1} q [0-9]\{|l| - x - 1\}$$$. Similarly for $$$r$$$, but here $$$q < r_x$$$. Also for all $$$|l| < x < |r|$$$ we should make regular expressions $$$[1-9][0-9]\{x - 1\}$$$, this is equal to nine expressions of our form. Notice that every modest number would satisfy exactly one regular expression and no other number would satisfy any expression.
Let's call wildcard of length $$$x$$$ tail of regular expression of form $$$[0-9]\{x\}$$$. Let's build Aho-Corasick automaton for all prefixes of regular expressions until wildcards. For every regular expression put in corresponding node length of wildcard. After that task could be solved using dynamic programming. State would be length of prefix of answer and node of the automaton. From state $$$(i, v)$$$ we can go by digit $$$d$$$ to the state $$$(i + 1, u)$$$, $$$u$$$ is node where $$$d$$$ leads from $$$v$$$. Value for $$$(i + 1, u)$$$ should be updated by value for $$$(i, v)$$$ plus number of wildcards with lengths not exceeding $$$n - i - 1$$$, placed in nodes reachable from $$$u$$$ by suffix links in automaton. This value can be calculated beforehand for every pair node and length. Asymptotics of solution is $$$O((|l| + |r|) \cdot n \cdot \Sigma ^ 2)$$$, where $$$\Sigma$$$ is size of alphabet, i.e. $$$10$$$.