trang chủ / đề bài / icpc21_bt_b

Xâu con tốt nhất

Đề bài

Mô tả

Cho một xâu s=s1s2s3…sn. Gọi f(s,i) là vị trí bắt đầu của xâu con độ dài i tốt nhất. Với hai xâu con a và b có cùng độ dài, xâu nào có thứ tự từ điển nhỏ hơn thì tốt hơn. Nếu hai xâu con giống nhau, xâu nào có vị trí bắt đầu nhỏ hơn thì tốt hơn.

Đặt h(s)=∑i=1ni×f(s,i). Nhiệm vụ của bạn là tính h(s).

Dữ liệu vào

  • Dòng đầu tiên chứa số bộ dữ liệu T.
  • Mỗi bộ dữ liệu là một dòng chứa một xâu s.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra h(s) trên một dòng.

Ràng buộc

  • 1≤T≤105.
  • 1≤|s|≤2×105.
  • Tổng độ dài các xâu không vượt quá 2×106.

Ví dụ

Input Output Giải thích
3
apple
banana
abcdabcd
15
36
36
Các vị trí được đánh số từ 1. Với "apple", xâu con tốt nhất của mọi độ dài đều bắt đầu ở vị trí 1, nên h=1+2+3+4+5=15. Với "banana", f=2 với i=1,…,5 (ví dụ "ana" xuất hiện ở vị trí 2 và 4, chọn vị trí nhỏ hơn) và f=1 với i=6, nên h=2·(1+2+3+4+5)+6=36.
1
a
1 Chỉ có một xâu con độ dài 1, bắt đầu ở vị trí 1.

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