題目簡述：給定$1 \leq l \leq r \leq 10^{800}$，求一個長度為$n \leq 2000$的數字串$s$，其含有最多的【好】子串。一個串$s$是【好】的，如果將其看做數字時無前導零且滿足$l \leq s \leq r$。形式化的說，就是求

$$ \arg \max_{s \in \Sigma^n} \sum_{i=1}^n \sum_{j=i}^n [s[i] \neq 0 \land l \leq s[i \dots j] \leq r] , $$

其中$\Sigma = \{0,1,2,\dots, 9\}$。

解：code

Step 1. 用一類特殊的 正規/正則 語言（Regular Language）描述$l \leq x \leq r$

我們選擇一類特殊的正規語言，其形如 $ L = d \Sigma^m $，其中$d \in \Sigma^+, m \in \mathbb{N}$。

觀察：存在一組不相交的上述特殊的正規語言$L_1, L_2, \dots, L_k$，使得

$$ \bigcup_{i=1}^k L_i = \mathbb{N} \cap [l, r] $$

且$k = O(|\Sigma|(\log l+\log r))$。

這個結論我們不加證明，但給出兩個例子以說明。

Example 1. $l = 12, r = 1234$。我們可取：

$$
\begin{aligned}
&?12, 13, 14, 15, 16, 17, 18, 19, \\
&?2\Sigma^1, 3\Sigma^1, \dots, 9\Sigma^1, \\
& 1\Sigma^2, 2\Sigma^2, \dots, 9\Sigma^2, \\
& 10\Sigma^2, 11\Sigma^2, \\
& 120\Sigma^1, 121\Sigma^1, 122\Sigma^1, \\
& 1230, 1231, 1232, 1233, 1234.
\end{aligned}
$$

Example 2. $l = 1234, r = 1456$。我們可取：

$$
\begin{aligned}
& 1234, 1235, 1236, 1237, 1238, 1239, \\
&?124\Sigma^1, 125\Sigma^1, \dots, 129\Sigma^1, \\
&?13\Sigma^2, \\
& 140\Sigma^1, 141\Sigma^1,?142\Sigma^1,?143\Sigma^1,?144\Sigma^1, \\
& 1450, 1451, 1452, 1453, 1454, 1455, 1456.
\end{aligned}
$$

Step 2：構建一組特殊正規語言的 AC自動機（Aho-Corasick? Automaton）

我們可以把$L = d \Sigma^m$這類特殊的正規語言簡記為$(d, m)$，分別稱為$d$部分和$m$部分。對于$L_1, L_2, \dots, L_k$，其中$L_i = (d_i, m_i)$，我們構建包含單詞$d_1, d_2, \dots, d_k$的AC自動機。值得一提的是，由于$L_i$的構造的局部特征，AC自動機的狀態數是$O(|\Sigma|(\log l+\log r))$的。

注：AC自動機也是一類（確定）有限狀態自動機（(Deterministic) Finite-State Automaton），因此其也可描述成一個有限狀態自動機，其狀態集為$Q$，初始狀態為$q_0 \in Q$，轉移函數為$\delta: \Sigma \times Q \to Q$。

Step 3：動態規劃

設$f[q][i]$表示：長度為$n$且滿足$\delta(q_0, s[1\dots i]) = q$的那些數字串$s$中，$d$部分在$s[1\dots i]$內的$s$的【好】子串的最大個數。則

$$ f[q][i] = \max_{p \to q} \{ f[p][i-1] \}+g[q][n-i], $$

其中$p \to q$表示存在$a \in \Sigma$使得$\delta(p, a) = q$，$g[q][L]$表示$d$部分恰好在$q$處結束且$m$部分長度不超過$L$的正規語言個數，即

$$ g[q][L] = \sum_{i=1}^k [d_i \in \text{pre}(q) \land m_i \leq L], $$

其中$\text{pre}(q) = \{ q, \text{link}(q), \text{link}(\text{link}(q)), \dots, q_0 \}$表示$q$在失敗樹上的所有祖先，而$\text{link}(q)$表示$q$在AC自動機中的失敗指針。

?

于是時間復雜度為$O(|\Sigma|^2 n(\log l+\log r))$，通過一些小優化可將時間復雜度降為$O(|\Sigma| n (\log l+\log r))$。

?

轉載于:https://www.cnblogs.com/TinyWong/p/10394579.html

總結

以上是生活随笔為你收集整理的CodeForces 1110H. Modest Substrings的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。