Ghép Mẫu Lặp Lại

Buổi 64 — Contest Chặng 7
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho chuỗi văn bản T có độ dài N và chuỗi mẫu P có độ dài M. Tìm tất cả các vị trí xuất hiện của P trong T. Sau đó, với mỗi vị trí xuất hiện i, tính giá trị f(i) = i * (i + M - 1) mod (10^9 + 7). In ra tổng tất cả f(i) mod (10^9 + 7).

Dữ liệu vào

Dòng 1: Chuỗi T (1 ≤ |T| ≤ 10^6) Dòng 2: Chuỗi P (1 ≤ |P| ≤ |T|)

Dữ liệu ra

Một số nguyên duy nhất — tổng f(i) mod (10^9 + 7). Các vị trí đánh số từ 1.

Ví dụ
Input Output
ababab\nab 44
Giới hạn
  • 1 ≤ |P| ≤ |T| ≤ 10^6
  • Chuỗi chỉ gồm chữ cái thường
Draft saved