Xâu: hashing, KMP, Z
40 bài xử lý xâu, độ khó tăng dần (rating 1100 đến 2400): xâu cơ bản và palindrome, hashing, hàm tiền tố (KMP), Z-function, Manacher, xoay vòng nhỏ nhất, trie và trie XOR, Aho-Corasick, mảng hậu tố.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
cmpsub
Điểm4,00
So sánh hai đoạn xâu
Băm đa thức tiền tố so sánh đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
kmpcnt
Điểm5,00
Đếm xuất hiện không chồng lấp
KMP + tham lam xuất hiện không chồng lấp
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
longpalin
Điểm1,00
Palindrome Dài Nhất
Manacher: palindrome dài nhất
Chưa phân loại
Tỷ lệ AC
75,0%
AC
3
subsk
Điểm5,00
Đếm xâu con độ dài k phân biệt
Băm lăn đếm xâu con độ dài k phân biệt
Chưa phân loại
Tỷ lệ AC
20,0%
AC
1
xorsubarray
Điểm1,00
XOR Mảng Con Lớn Nhất
Trie nhị phân: XOR đoạn con lớn nhất
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
campsched
Điểm5,00
Lịch trại
Hàm tiền tố: chồng lấp tối đa bản sao
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
zfunbord
Điểm5,00
Đếm biên (border) của mỗi tiền tố
Z-function + mảng hiệu đếm biên mọi tiền tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
allpalin
Điểm5,00
Tất Cả Palindrome
Manacher: palindrome dài nhất kết thúc tại i
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
dhbb25_dx45_10_password
Điểm5,00
Mật khẩu tuần hoàn
Băm: kiểm tra chu kỳ đoạn qua các ước
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
invsfxarr
Điểm1,00
Mảng Hậu Tố Nghịch
Dựng xâu từ mảng hậu tố qua rank
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
kbadsub
Điểm6,00
Xâu con tốt
Đếm xâu con phân biệt thỏa điều kiện (băm/trie)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
prefsufpal
Điểm6,00
Xâu đối xứng tiền tố - hậu tố
Palindrome tiền tố dài nhất qua hàm tiền tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhbb26_dx34_11_b
Điểm6,00
Tìm đất xây biệt thự
So khớp mẫu 2D: Aho-Corasick theo dòng + KMP cột
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi13_msg
Điểm6,00
Trao đổi thông tin
Băm 2D + chặt nhị phân bảng chung lớn nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
first
Điểm1,00
Xếp đầu tiên
Trie + đồ thị ràng buộc thứ tự chữ cái
Chưa phân loại
Tỷ lệ AC
60,0%
AC
1
borderocc
Điểm7,00
Tiền tố trùng Hậu tố
Hàm tiền tố: biên và số lần xuất hiện
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
onediff
Điểm7,00
Khác đúng một vị trí
Băm: sinh 2L xâu khác một vị trí
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
commander
Điểm7,00
Chọn chỉ huy
Trie nhị phân có đếm: số x XOR p nhỏ hơn l
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhbb25_dx08_10_matching
Điểm7,00
Biển quảng cáo
KMP so khớp bảo toàn thứ tự
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
qt_tst_24_a
Điểm7,00
Xâu đối xứng đôi
Manacher + ghép hai tâm đối xứng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
palinq
Điểm1,00
Truy Vấn Palindrome
Băm xuôi ngược trên segment tree
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
subbe
Điểm7,00
Đếm xâu con đầu–cuối phân biệt
Vị trí xuất hiện + băm đếm xâu phân biệt
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
supstr3
Điểm8,00
Xâu chứa ba xâu con
KMP chồng lấp, thử 6 thứ tự ghép
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
paldeg
Điểm8,00
Bậc đối xứng
Băm xuôi ngược kiểm tra tiền tố đối xứng
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
martstr
Điểm8,00
Xâu Sao Hỏa
Hàm tiền tố hai chiều, ghép tiền tố và hậu tố
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
distsubstr
Điểm1,00
Xâu Con Phân Biệt
Mảng hậu tố + LCP đếm xâu con phân biệt
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc22_mn_j
Điểm8,00
Không phải bài toán xâu kinh điển
Mảng hậu tố + LCP, đếm offline bằng BIT
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
encstr
Điểm8,00
Mã hóa xâu con
Băm theo từng chữ cái, ghép phép thế
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
standingout
Điểm1,00
Nổi Bật Trong Đàn
Mảng hậu tố tổng quát nhiều xâu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
pt_tst_25_f
Điểm8,00
Đếm chuỗi con
Aho-Corasick + đếm offline trên đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0