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.|

PTIT017I - ACM PTIT 2017 I - VIRUS

“TextFile” là một virus chuyên tấn công các file văn bản theo phương thức sau: Sao chép một đoạn các ký tự liên tiếp trong nội dung của file văn bản vào bộ nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản.

Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự T và số nguyên không âm k, xâu con gồm các ký tự từ vị trí p đến vị trí q của xâu T được gọi là đoạn có khả năng bị virus sao chép mức k nếu nó sai khác với xâu con gồm các ký tự từ vị trí q+1 đến vị trí q+(q-p+1) của xâu T ở không quá k vị trí.

Ví dụ, xét xâu T = ‘zabaaxy’ và k = 1. Đoạn văn bản ‘ab’ từ ký tự thứ 2 đến ký tự thứ 3 là đoạn văn bản độ dài 2 có khả năng bị virus sao chép mức 1 vì nó khác với đoạn văn bản ‘aa’ gồm các ký tự từ ký tự thứ 4 đến ký tự thứ 5 của xâu T ở 1 vị trí.  

Yêu cầu: Cho xâu ký tự Tn số nguyên không âm k1, k2,…, kn. Với mỗi giá trị ki, hãy tìm độ dài đoạn dài nhất trong xâu T có khả năng bị virus sao chép mức ki  (i = 1, 2,…, n).

Input

  • Dòng đầu chứa số nguyên dương n (n ≤ 10);
  • Dòng thứ hai chứa một xâu T gồm các chữ cái in thường lấy từ tập 26 chữ cái tiếng Anh từ ‘a’ đến ‘z’ (độ xâu T không vượt quá 300);
  • Dòng thứ i trong số n dòng tiếp theo ghi số nguyên không âm ki (ki ≤ 10, i = 1, 2,…, n).

Output

Gồm n dòng, dòng thứ i ghi một số nguyên không âm là độ dài đoạn dài nhất có khả năng bị virus sao chép mức ki, i=1, 2,…, n. Ghi 0 nếu không tìm được đoạn như vậy.

Example

Test 1:
Input:
2
zabaaxy
0
1 Output: 1
2
Test 2:
Input:
2
zcaabcaaaa
0
1
Output:
2
4

Giải thích: Trong ví dụ bên phải, đoạn dài nhất có khả năng bị virus sao chép mức 0 là ‘aa’ có độ dài 2, đoạn dài nhất có khả năng bị virus sao chép mức 1 là ‘caab’ có độ dài 4.


Được gửi lên bởi:Admin
Ngày:2017-04-29
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 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

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