Being a class monitor, you have a list of names of your class students. Your task is to find the first name from the list, which is similar to any other name occurring before it in the list.
Two names, name1 and name2, are similar if at least one of the following conditions holds.
Both names are identical. name1 is a prefix of name2. name2 is a prefix of name1.
Print the first name from the list, which is similar to any other name present in the prefix part of the list. If no such name is found, print “not found”.
1 <= 'T' <= 5 1 <= 'N' <= 10^5 1 <= the length of name[i] <= 60 i ∈ (1,N) All letters in name[i] are lowercase english letters, in the range 'a' to 'j' inclusive. Note - Sum of 'N' over all test cases does not exceed 10^5. Time Limit: 1 sec
Sample Output 1 :
2 4 aab aac aacgh aabgh 3 abc aba baa
Explanation for Sample Input 1 :
aacgh not found
Sample Input 2 :
For case 1: Start checking from the first name to the last. For "aab", a similar name is "aabgh", but that's not present in the prefix list. For "aac", a similar name is "aacgh", but that’s also not present in the prefix of list. For "aacgh", similar name is "aac" which is present in prefix of list. Hence our answer is "aacgh". For Case 2: No name in the list is similar to any other name. Hence print "not found".
Sample Output 2 :
2 3 ab abb abbb 2 dc d