java - Search for a sub-string in a given array of strings in android -

i have array of n strings. want select elements of array has given string.

sorry if not clear. i'll give example.

input = "as" array = {"abas", "aras", "as", "ask", "asi", "aso", "atas", "best", "test"} output = {"abas", "aras", "as", "ask", "asi", "aso", "atas"} 

which algorithm need selection. need fastest algorithm perform operation since i'm using autocomplete in android search should faster typing speed of user. have total 20000 entries.

note: if want show strings start input, read this.

as want strings start given input, string matching algorithm kmp or boyer moore not going give results. because have iterate on string in array , compare(if want want suffix, kmp not better linear search).

a better option construct trie array , when want show result of autocomplete, traverse through array , show words under current node.

for input array = ["abas", "aras", "as", "ask", "asi", "aso", "atas" ,"best","test"] corresponding trie : ('.' represents end of string)

i did not add test structure best

            dummy           /       \                  b        / | \       |        b  r  s      est.      /   |   ?      as.  as. 

the tree in place of ? :

              s.             / | \            k. i.  o. 

when want search strings start as, have traverse in path as , print words under it. here {as,ask,asi,aso}