Chef And Special Dishes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
One day, Chef prepared D brand new dishes. He named the i-th dish by a string Si. After the cooking, he decided to categorize each of these D dishes as special or not.
A dish Si is called special if it's name (i.e. the string Si) can be represented in the form of a double string by removing at most one (possibly zero) character from it's name from any position.
A string is called a double string if it can be represented as a concatenation of two identical, non-empty strings. e.g. "abab" is a double string as it can be represented as "ab" + "ab" where + operation denotes concatenation. Similarly, "aa", "abcabc" are double strings whereas "a", "abba", "abc" are not.
- First line of the input contains an integer D denoting the number of dishes prepared by Chef on that day.
- Each of the next D lines will contain description of a dish.
- The i-th line contains the name of i-th dish Si.
For each of the D dishes, print a single line containing "YES" or "NO" (without quotes) denoting whether the dish can be called as a special or not.
- 1 ≤ D ≤ 106
- 1 ≤ |Si| ≤ 106.
- Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').
Subtask #1 : (20 points)
- Sum of |Si| in an input file doesn't exceed 2 * 103
Subtask 2 : (80 points)
- Sum of |Si| in an input file doesn't exceed 2 * 106
Input: 3 aba abac abcd Output: YES NO NO
Example case 1. We can remove the character at position 1 (0-based index) to get "aa" which is a double string. Hence, it is a special dish.
Example case 2. It is not possible to remove the character at any of the position to get the double string. Hence, it is not a special dish.
|Tags||march16, prateekg603, simple, string|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.