S*********r
发帖数: 5693 | 1 Lets say you have 1 string of length N and M small strings of length L. How
do you efficiently find the occurrence of each small string in the big
string ? |
f****g
发帖数: 313 | 2 Need to preprocess the string of length N
for example the string, "abcayazbc"
abcayazbc
bcayazbc
cayazbc
ayazbc
yazbc
azbc
zbc
bc
c
Save the list of the strings in the Trie.
for each small string, the matching just takes O(L), L is the length of the
small string. |
s*******e
发帖数: 93 | 3 build a suffix tree for the long string? |
m*******i
发帖数: 8711 | 4 typical search indexing problem. |
H******7
发帖数: 1728 | |
j********x
发帖数: 2330 | 6 build a DFA/NFA of M shorter strings.
I am pretty sure that the interviewer will not be satisfied by this answer..
. |
