Chuỗi Con Chung Dài Nhất Hai Chuỗi

Binary-search Buổi 53 — String Hashing
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho hai chuỗi $S$ và $T$ gồm các ký tự in thường. Hãy tìm độ dài chuỗi con (substring) chung dài nhất của $S$ và $T$.

Sử dụng hàm băm kết hợp tìm kiếm nhị phân.

Dữ liệu vào
  • Dòng đầu tiên chứa chuỗi $S$.
  • Dòng thứ hai chứa chuỗi $T$.
Dữ liệu ra
  • In ra một số nguyên — độ dài chuỗi con chung dài nhất.
Ví dụ
Input Output
abcdef\nzbcdf 3
abc\nxyz 0
Giới hạn
  • $1 \le |S|, |T| \le 10^5$
  • Chuỗi chỉ chứa ký tự in thường từ a đến z.

Giải thích ví dụ 1: Chuỗi con chung dài nhất là bcd có độ dài 3.

Draft saved