Đếm Xâu Con Chỉ Thuộc Chuỗi Thứ Nhất

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

Cho hai chuỗi ký tự $A$ và $B$ chỉ gồm các chữ cái tiếng Anh in thường. Bạn cần đếm xem có bao nhiêu xâu con khác rỗng phân biệt xuất hiện trong chuỗi $A$ nhưng hoàn toàn không xuất hiện (dưới dạng xâu con liên tiếp) ở bất kỳ đâu trong chuỗi $B$. Hai xâu con được coi là giống nhau nếu chúng có cùng nội dung ký tự, bất kể vị trí xuất hiện trong $A$.

Dữ liệu vào

Dòng đầu tiên chứa chuỗi $A$ ($1 \le |A| \le 10^5$). Dòng thứ hai chứa chuỗi $B$ ($1 \le |B| \le 10^5$). Cả hai chuỗi chỉ gồm chữ cái in thường 'a'..'z'.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng xâu con phân biệt của $A$ không có mặt trong $B$.

Ví dụ
Input Output
ababa
bab
4
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved