AT_xmascon23_f Failed Failure Link

如果字符串 $t$ 是字符串 $s$ 的 **border**，那么 $t$ 既是 $s$ 的前缀也是 $s$ 的后缀。对于长度为 $n$ 的字符串 $s$ 和满足 $1 \le k \le n$ 的整数 $k$，定义 $f(s, k)$ 为 $s$ 的长度为 $k$ 的前缀的 border 中，长度小于 $k$ 的 border 的最大长度（空字符串被认为是任何字符串的 border，因此该定义是合理的）。另外，规定 $f(s, 0) = -1$。 “しろうさ”打算实现一个算法，从长度为 $n$ 的字符串 $s$ 计算出 $f(s, 0), f(s, 1), \ldots, f(s, n)$。但他不小心写错了。函数 `Xmas` 用 C++ 代码片段如下，实现的实际计算结果为整数序列 $g(s, 0), g(s, 1),\ldots,g(s, n)$： ``` #include #include std::vector Xmas(std::string s) { int n = s.size(); std::vector g(n + 1); int j = g[0] = -1; for (int i = 0; i < n; ++i) { for (; j >= 0 && s[j] == s[i]; j = g[j]) {} g[i + 1] = ++j; } return g; } ``` 现在给定正整数 $A, B$。请你从 $A$ 个字符 `a` 和 $B$ 个字符 `b` 组成的、长度为 $A+B$ 的字符串 $s$ 中，求出 $ \displaystyle\sum_{k=0}^{A+B} |f(s, k) - g(s, k)| $ 的最小值，以及达到最小值的一个 $s$。

输入采用如下格式，从标准输入读入。 > $ A $ $ B $

第 $1$ 行输出 $ \displaystyle\sum_{k=0}^{A+B} |f(s, k) - g(s, k)| $ 的最小值。 第 $2$ 行输出一个能够达到最小值的 $s$。

### 样例解释 1 $f(\mathtt{aba}, 0) = -1,\, f(\mathtt{aba}, 1) = 0,\, f(\mathtt{aba}, 2) = 0,\, f(\mathtt{aba}, 3) = 1$。 $g(\mathtt{aba}, 0) = -1,\, g(\mathtt{aba}, 1) = 0,\, g(\mathtt{aba}, 2) = 1,\, g(\mathtt{aba}, 3) = 2$。 ### 数据范围 - $1 \le A, B \le 10^5$。 由 ChatGPT 5 翻译