C. Дэд тэмдэгт мөрийн олон төрөл

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тэмдэгт мөрийн олон төрөл нь наад зах нь нэг удаа тэмдэгт мөрд гарч ирж байгаа тэмдэгтүүдийн тоо юм. $s$-ийн олон төрлийг $d(s)$ илэрхийлнэ. Жишээлбэл: $d$("$aaa$")=1, $d$("$abacaba$")=3.

Латин жижиг үсгүүдээс бүрдсэн $s$ тэмдэгт мөр өгөгдсөн. Бүх дэд тэмдэгт мөрүүдийг авч үзье. Мэдээж хэрэг ямар ч дэд тэмдэгт мөрийн олон төрлийн тоо нь 41-ээс $d(s)$ байна. Дэд тэмдэгт мөрийн олон төрлийн талаарх статистик мэдээллийг олно: 1-ээс $d(s)$ хүртэлх $k$ бүрийн хувьд, $s$-д яг $k$-н олон төрөл хэд байгааг олно.

Оролт

Оролт нь $s$ тэмдэгт мөрийг агуулсан нэг мөрөөс бүрдэнэ. Энэ нь зөвхөн Латин жижиг үсгүүд байх ба $s$-н урт нь 1-ээс $3*10^{5}$-н хооронд байна.

Гаралт

Эхний мөрөнд $d(s)$-н утгыг хэвлэнэ. Дараагийн мөрүүдэд $t_{1}, t_{2}, ..., t_{d(s)}$ дарааллыг хэвлэнэ. $t_{i}$ нь $s$-д байгаа дэд тэмдэг мөрүүдийн яг $i$-н олон төрлийн тоо.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
abca
Гаралт
3
4
3
3
Оролт
aabacaabbad
Гаралт
4
14
19
28
5

Тэмдэглэл

Эхний жишээг авч үзье.

Бид "$abca$"-н $[i, j]$ индекстэй хэсгийн дэд тэмдэгт мөрийг $s(i, j)$ илэрхийлнэ.

  • $s(1, 1) = $ "a$", $d($"a$"$) = 1$
  • $s(2, 2) = $ "b$", $d($"b$"$) = 1$
  • $s(3, 3) = $ "c$", $d($"c$"$) = 1$
  • $s(4, 4) = $ "a$", $d($"a$"$) = 1$
  • $s(1, 2) = $ "ab$", $d($"ab$"$) = 2$
  • $s(2, 3) = $ "bc$", $d($"bc$"$) = 2$
  • $s(3, 4) = $ "ca$", $d($"ca$"$) = 2$
  • $s(1, 3) = $ "abc$", $d($"abc$"$) = 3$
  • $s(2, 4) = $ "bca$", $d($"bca$"$) = 3$
  • $s(1, 4) = $ "abca$", $d($"abca$"$) = 3$

1 олон төрөлтэй 4, 2 олон төрөлтэй 3, 3 олон төрөлтэй 3-н дэд тэмдэгт мөр байна.

Сэтгэгдлүүдийг ачааллаж байна...