← 返回题目列表

AtCoder · xmascon23_f

F. 失败的失败链接

中文机器翻译题面 查看原题

配点 : 100 点

黑兔「还有找错误游戏哦!」

問題文

文字列 t 是字符串 s 可以得到第 border 意味着t 是 在 s 的前缀同时也是后缀。长度 n 的字符串 s 和整数 可以获得第 1 \le k \le n , 定义f(s, k) ,s 的长度 k 的前缀 border,并且长度小于 k 的是其中最长的长度(空字符串是任何字符串的 border,因此这是定义明确的)。另外,f(s, 0) = -1 被定义为。

当给定长度 n 的字符串 s 时,白兔 f(s, 0), f(s, 1), \ldots, f(s, n) 的算法,但搞错了。给定以下C++代码片段表示的函数 Xmas 至 该值是 s 作为参数时,会计算出的整数序列是 g 该值应乘以 (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} \bigl\lvert f(s, k) - g(s, k) \bigr\rvert 的最小值,以及达到最小值的 s 该值应乘以 1 找到一个。

制約

  • 1 \le A, B \le 10^5.

入力

输入是按以下格式从标准输入给出的。

A B

出力

1 行上, 输出\displaystyle\sum_{k=0}^{A+B} \bigl\lvert f(s, k) - g(s, k) \bigr\rvert 的最小值。在第

2 行,最小值会被实现。在兔子和猫的国度里,现在 s 出 1 输出一。


入力例 1

2 1

出力例 1

2
aba

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 是。