CareerCup

Need to Construct a Trie Searching, (Compressed Trie)

A hash table.
insert the first array and find if an element of the second array exists in the constructed hash table.
if it exists, store the index. finally we have indices of the strings in the second array which are common to both arrays

Method 1:
1. Make a concatenated string of S2 using some delimiter. Say dot (.)
e.g. ConcatS2 = ".Kelos.Dragi.Matt.Ven.Pssi."
2. Pick a word from S1 add delimiter at end and start. Use KMP to serach this pattern in ConcatS2.
e.g. Pick first word "Albert", make pattern as ".Albert." and search in ConcatS2.
**Asumption delimiter is not used in any of original S1 and S2 as a character.
Time Complexity: If S1 contains m number of words and total length of S2 is N then it is m*O(N). Average case will be less than this (Words are Unique)
Method2:
1. Make a trie of S2. Look for each word of S1 if it exist in trie.
Time Complexity: O(length of S1).

An unordered_map should do the trick!

O(m+n) time and O(m) space... where m and n are lenghts of the sets...

- Add all elements from set1 to u_map_1...
- For every element in set 2, check if it is present in u_map_1...
- If it is present, print it out to the console.

PS: Looking for a value in an unordered_map takes O(1) since the keys are hashed.