Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.