| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P152SUMJ - ROUND 2J - Truy vấn trên xâu |
Cho một xâu s, một chuỗi con của xâu s là một đoạn các kí tự liên tiếp của s.
Định nghĩa hàm F(x, y) như sau. Với tất cả các cặp số (l, r) tương ứng với một chuỗi con của x thỏa mãn chuỗi con này bằng xâu y. Sắp xếp lại các cặp số này theo vị trí bắt đầu tăng dần, ta được một danh sách với các phần từ là các cặp số.
Số lượng các dãy con gồm các phần tử của danh sách chính là giá trị của hàm F(x, y).
Ví dụ: F(babbabbababbab, babb) = 6.
Các cặp vị trí là: (1, 4), (4, 7), (9, 12). Ta sẽ được các dãy con của danh sách như sau:
- (1, 4)
- (4, 7)
- (9, 12)
- (1, 4), (4, 7)
- (4, 7), (9, 12)
- (1, 4), (4, 7), (9, 12)
Nhiệm vụ của bạn là tính tổng các hàm F(s, x) với x thuộc tập các chuỗi con của s, các xâu con giống nhau tính là 1.
Input
Một dòng duy nhất chứa xâu s, gồm các chữ cái latinh thường. Độ dài xâu không quá 10^5
Output
Dòng duy nhất chứa kết quả bài toán.
Example
Test 1:
Input:
aaaa
Output:
20
Test 2:
Input:
abcdef
Output:
21
Test 3:
Input:
abacabadabacaba
Output:
188
Giải thích: Test 1 với các xâu “a”, “aa”, “aaa”, “aaaa” kết quả lần lượng là 10, 6, 3, 1.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-08 |
| Thời gian chạy: | 2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
