trang chủ / đề bài / icpc26_nat_k

Xâu con k-đều

Đề bài

Mô tả

Cho xâu S gồm các chữ cái tiếng Anh in hoa. Với một số nguyên dương k, một xâu con k-đều của S là một xâu con gồm k ký tự liên tiếp của S mà tất cả đều là cùng một chữ cái. Hai xâu con k-đều được coi là khác nhau nếu chúng bắt đầu ở hai vị trí khác nhau. Ví dụ, xâu AAAB có hai xâu con 2-đều (cả hai đều là AA, bắt đầu ở vị trí 1 và 2) và một xâu con 3-đều.

Bạn được phép đổi nhiều nhất một ký tự của S thành một chữ cái tiếng Anh in hoa bất kỳ. Với mỗi k=1,2,…,|S|, hãy tìm số lượng xâu con k-đều nhỏ nhất có thể của S sau khi đổi. Lưu ý rằng cách đổi được chọn độc lập cho từng k.

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤104). Tiếp theo là mô tả các bộ dữ liệu.

Mỗi bộ dữ liệu gồm một dòng duy nhất chứa xâu S (1≤|S|≤106) gồm các chữ cái tiếng Anh in hoa.

Dữ liệu đảm bảo tổng |S| qua tất cả các bộ dữ liệu không vượt quá 106.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm |S| số nguyên. Số nguyên thứ k là số lượng xâu con k-đều nhỏ nhất có thể của S sau khi đổi nhiều nhất một ký tự.

Ràng buộc

  • 1≤τ≤104.
  • 1≤|S|≤106; S chỉ gồm các chữ cái tiếng Anh in hoa.
  • Tổng |S| qua tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
2
Z
AAB
1
3 0 0
Bộ thứ nhất: dù đổi thế nào, xâu một ký tự luôn có đúng một xâu con 1-đều. Bộ thứ hai: mỗi ký tự luôn là một xâu con 1-đều nên với k=1 đáp án là 3; đổi ký tự giữa thành C được ACB, không còn xâu con 2-đều hay 3-đều nào.
2
AAAAA
ABBBBA
5 2 0 0 0
6 1 0 0 0 0
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: đổi ký tự giữa được AABAA, còn hai xâu con 2-đều (AA ở đầu và ở cuối) và không còn xâu con 3-đều nào. Bộ thứ hai: đổi thành ABBCBA còn một xâu con 2-đều (BB); xâu này cũng không còn xâu con 3-đều nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0