| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P184PROG - ROUND 4G - Xâu hoán vị cực đại |
Một xâu kí tự S độ dài n được biểu diễn dưới dạng S1S2S3…Sn trong đó Si là kí tự thứ i của xâu S. Một xâu P là xâu hoán vị của xâu S nếu P = Sp1Sp2Sp3…Spn, trong đó p1, p2, p3, …, pn là một bộ hoán vị của các số tự nhiên từ 1 đến n.
Cho 2 xâu kí tự T và V. Trong các xâu hoán vị của T, hãy tìm ra xâu có số lần xuất hiện trong xâu V là nhiều nhất. Nếu có nhiều xâu như vậy, chọn ra xâu có thứ tự từ điển nhỏ nhất.
Input
Dòng đầu gồm một số nguyên dương Q (1 ≤ Q ≤ 3) là số bộ test.
Mỗi bộ test gồm 2 dòng, dòng đầu tiên là xâu T, dòng thứ 2 là xâu V (1 ≤ |T| ≤ 20000, 1 ≤ |V| ≤ 200000, |T| ≤ |V|).
Các xâu ký tự chỉ gồm các chữ cái tiếng Anh viết thường.
Output
Với mỗi bộ test, in ra trên một dòng xâu hoán vị tìm được. Nếu không có xâu nào thoả mãn, in ra -1.
Example
Input: 2
tan
tantant
t
v Output: ant
-1
Giải thích:
Ở ví dụ 1, xâu ‘tan’ có 3 xâu hoán vị xuất hiện trong xâu ‘tantant’ là ‘ant’, ‘nta’ và ‘tan’. Trong đó ‘ant’ và ‘tan’ cùng có số lần xuất hiện lớn nhất là 2, do đó ta chọn ‘ant’ vì nó có thứ tự từ điển nhỏ hơn.
| Được gửi lên bởi: | adm |
| Ngày: | 2018-03-23 |
| 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 PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
