如何提高大量字符串查找操作的效率（非前缀搜索）？

Question

问题：
有一个比较大的字符串数组[A]，10万左右元素，每个元素是比较短的字符串，长度小于32个字.
用户输入一个比较短的字符串s，长度也小于32，要求查找出：包含s的元素集合[B]，拼音中包含s的元素集合[C]，以及拼音首字母中包含s的元素集合[D]. 要求支持多音字和中英文数字混输.

功能我已经实现了，但是现在项目要求随着用户在输入框中输入，结果实时地在输入框中显示，我的实现比较慢，做不到随输随显示。如果想提高效率，该用什么办法呢？

我把计算拼音和拼音首字母的结果做了缓存，提高了一些效率，但是还是达不到要求。

我的想法是：
1.能不能用某种数据结构把[A]重新组织起来方便查找？
2.因为结果是在QTreeView中显示的，这里能不能优化一下？

注：
1.不是前缀搜索，是只要包含子串s的都找出来。
2.要支持多音字，所以一个字符串可能对应很多个拼音串。

Answer 1

如果字符串大小小于32的话，你可以考虑生成32棵trie树.基本思路是这样的吧，用户每次查找都在这32棵树中进行搜索。假设字符串长度限制为4个为例：
原始字符串
1234 2234 3234 4234
转换为：
t1: 1234+ 2234+ 3234+ 4234+
t2: 234+1 234+2 234+3 234+4
t3: 34+12 34+22 34+32 44+23
t4: 4+123 4+223 4+323 4+234

对t3:

-----nil-----
   |    |
   3    4
  ---  ---
   |      |
   4      4
  ---     ---
 +++++++   +++
 +  +  +     +
 12 22 32    23

+之后的节点只用来还原字符串，不参与查找。
当用户输入3时，首先匹配上t3，用户继续次输入时，只需要在t3树下继续查找即可。
举例：
用户输入34：
输入3： 先匹配t3,需要查找4次，
继续输入4：直接在t3中查找，1次即可

用户输入35：
输入3： 先匹配t3,需要查找4次，
继续输入5：直接在t3中查找，匹配不到，即是没有

内存占用提高32倍，算法时间基本为常量

Answer 2

我不是很懂你要表达的意思, 我猜是这样的:

你手里有10万个字符串, 需要查出给定字符串为前缀的所有字符串. 例如:

我有['abcde', 'abcdef', 'abc', 'a'] 四个字符串, 当给定字符串为'ab'的时候, 查出['abcde', 'abcdef', 'abc'].

如果是这个意思, 请使用trie树.

Answer 3

楼主，请问你最后的解决方法是什么，能提点一二不，有代码更好