Cặp Hậu Tố LCP Lớn

Buổi 56 — Suffix Array & LCP
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu $S$ gồm các chữ cái in thường và số nguyên $K$. Hãy đếm số cặp có thứ tự $(i, j)$ với $0 \le i < j < |S|$ sao cho LCP (tiền tố chung dài nhất) của hậu tố bắt đầu tại $i$ và hậu tố bắt đầu tại $j$ có giá trị lớn hơn hoặc bằng $K$.

Dữ liệu vào

Dòng đầu tiên chứa xâu $S$ ($1 \le |S| \le 10^5$). Dòng thứ hai chứa số nguyên $K$ ($1 \le K \le |S|$).

Dữ liệu ra

Một số nguyên duy nhất là số cặp $(i, j)$ thỏa mãn.

Ví dụ
Input Output
banana\n1 7
Giới hạn
  • $1 \le |S| \le 10^5$
  • $1 \le K \le |S|$
Draft saved