| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT015J - ACM PTIT 2015 J- Xâu con lặp lại |
Cho một xâu S có tối đa 100000 chữ cái. Các xâu con lặp lại được định nghĩa là một đoạn liên tiếp các ký tự được lặp lại ít nhất hai lần trong xâu S (các đoạn có thể chồng lấn lên nhau).
Ví dụ xâu “aabaab” có 5 xâu con lặp lại là “a”; “aa”, “aab”, “ab”, “b”.
Xâu “aaaaa” sẽ có 4 xâu con lặp lại là “a”, “aa”, “aaa”, “aaaa”.
Bài toán đặt ra là cho trước một xâu không quá 100000 ký tự chữ cái, hãy đếm số xâu con lặp lại của xâu đó.
Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu ghi số bộ dữ liệu (không quá 10).
Mỗi bộ dữ liệu ghi trên một dòng xâu S tương ứng.
Output
Với mỗi bộ dữ liệu, ghi trên một dòng số xâu con lặp lại đếm được. Kết quả được đảm bảo không quá giới hạn số nguyên 32 bít.
Example
Input: 3
aabaab
aaaaa
AaAaA Output: 5
4
5
| Được gửi lên bởi: | adm |
| Ngày: | 2015-04-19 |
| Thời gian chạy: | 1s |
| 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 |
