NHREMIND - Reminding Password
Giới hạn- Thời gian: 5.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bờm có một mật khẩu rất rất là dài, và nó được ghi trong một tờ giấy.
Thật là lộ liệu và nguy hiểm nếu tờ giấy đó lọt vào tay người khác. Để dấu xâu mật khẩu A của mình, Bờm đã ghi thêm N xâu khác – gọi đó là các xâu B[1], B[2], … B[N]. Và ghi nhớ một xâu con E (gồm các kí tự liên tiếp) của A mà không là xâu con (gồm các kí tự liên tiếp) của bất cứ xâu B nào. Để khi nhìn lại tờ giấy, Bờm còn biết được đâu mới là mật khẩu của mình.
Tất nhiên là Bờm sẽ tìm xâu E có độ dài nhỏ nhất vì tính dễ quên của mình.
Input
- Dòng đầu tiên là số lượng xâu ghi thêm - N;
- N dòng tiếp theo, dòng thứ i ghi xâu B[i] khác rỗng;
- Dòng cuối cùng là xâu A - mật khẩu của Bờm;
Output
- Một dòng duy nhất là xâu E cần tìm - nếu có nhiều xâu thỏa, hãy in ra xâu có thứ tự từ điển nhỏ nhất.
Example
Input: 1
abacad
abbcaaa
Output: aa
Giới hạn
- LA = Length(A) <= 1000000 (Length(A) là độ dài xâu A);
- S = Length(B[1]) + Length(B[2]) + ... + Length(B[n]) <= 1000000;
- Các xâu chỉ gồm chữ cái la tin 'a'..'z';
- Có 50% số test LA, S <= 100;
- Người up: yellowflash12
- Nguồn bài: C11 Contest Round 22 - Trần Anh Hướng Thái Huy