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 <string>
#include <vector>
std::vector<int> Xmas(std::string s) {
  int n = s.size();
  std::vector<int> 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 翻译