I have an assignment that requires reading a huge file of random inputs, for example:
Adana
Izmir Adnan Menderes Apt
Addis Ababa
Aden
ADIYAMAN
ALDAN
Amman Marka Intl Airport
Adak Island
Adelaide Airport
ANURADHAPURA
Kodiak Apt
DALLAS/ADDISON
Ardabil
ANDREWS AFB
etc..
If I specify a search term, the program is supposed to find the lines whereby a substring occurs. For example, if the search term is "uradha", the program is supposed to show ANURADHAPURA. If the search term is "airport", the program is supposed to show Amman Marka Intl Airport, Adelaide Airport
A quote from the assignment specs: "You are to program this application taking efficiency into account as though large amounts of data and processing is involved.."
I could easily achieve this functionality using a loop but the performance would be O(n). I was thinking of using a trie but it seems to only work if the substring starts from index 0.
I was wondering what solutions are there which gives a performance better than O(n)?