Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which can match any character. For eg. if I add strings "abcd" and "abed" then search for "ab.d" should return me both of them.
I tried to tackle this using prefix Tries. It works fine for normal string search(without dot) but for dot I have to search for every child of a node. Is there a more efficient way of solving this problem?
This problem was considered in the following papers:
Partial-match retrieval algorithms. Ronald L. Rivest. SIAM Journal of Computing, volume 5, number 1, March 1976.
Fast Text Searching for Regular Expressions or Automaton Searching on Tries. Ricardo A. Baeza-Yates, Gaston H. Gonnet. Journal of the ACM, volume 43, number 6, 1996.
See also String matching for wildcard-based records, Given a set of string patterns, find which ones match a particular string, https://cstheory.stackexchange.com/q/36913/5038.
