Fastest algorithm to find a string in an array of strings?
algorithm
Solution
You could convert the whole array of strings to a finite state machine, where the transitions are the characters of the strings and put the smallest index of the strings that produced a state into the state. This takes a lot of time, and may be considered indexing.
Problem
This question is merely about algorithm. In pseudo code is like this: ``` A = Array of strings; //let's say count(A) = N S = String to find; //let's say length(S) = M for (Index=0; Index<count(A); Index++) if (A[Index]==S) { print "First occurrence at index\x20"+Index; break; } ``` This for loop requires string comparison N times (or byte comparison N*M times, O(N*M)). This is bad when array A has lots of items, or when string S is too long. Any better method to find out the first occurrence? Some algorithm at O(K*logK) is OK, but preferable at O(K) or best at O(logK), where K is either N or M. I don't mind adding in some other structures or doing some data processing before the comparison loop.