如何快速搜索40个单词的列表？

Question

如何快速搜索包含4000万字的列表？

我需要找到包含至少4个字母的单词,这些字母是我在继续之前指定的.

示例:列表中的字数很少:

dogging
dopping
baobabisaneviltree

我的特定字母是字符串格式'odxxini'.我需要从我的字符串中找到包含任何(4+)字符的任何单词.

结果:

dopping
dogging

(因为,这两个词都包含'o''d''我'n')我希望我解释得很好.对不起,英语.请纠正错误.

如果有人对这个问题有任何了解,我会很高兴听到他.:)

我写到目前为止(因为它是开头..)这段代码:

private void seeksearcher()
        {
            double counter = 0, k=0;
            double licznik = (double)listwords.Capacity;

            char[] letterarray = stringletters.ToCharArray();
            foreach(String word in listwords)
            {

                for(int i=0;i<letterarray.Length;i++)
                    if(word.Contains(letterarray[i]))
                        counter++;
                if(counter > 4)
                    textBox2.Text+=word + Environment.NewLine;

            }
        }

我很确定复杂性现在是n*7n,它的丑陋大:(

Answer 1

首先,显然没有解决方案比解决方案集的大小更快.如果您碰巧有一个匹配词典中每个单词的搜索字符串,那么枚举解决方案集需要枚举词典.

假设每个解集的大小与词典的大小相比非常小.

我们还假设词典中每个条目的大小都很短; 你在那里没有任何一万个字母的单词,或者那些愚蠢的东西.

鉴于这两个约束,最大的问题是你需要次线性搜索时间吗？

线性时间算法很简单.例如:

• 将每个词典单词的字符按字母顺序排序.
• 将查询的字符按字母顺序排序
• 对排序的词典中的每个单词进行排序查询的序列比较.

也就是说,假设你有词典

STOPPING
POTSHARD
OPTING
DECORATE

和查询TOPSXZ.按字符排序查询:OPSTXZ.现在浏览词典,按字符排序:

STOPPING --> GINOPPST
POTSHARD --> ADHOPRST
OPTING   --> GINOPT
DECORATE --> ACDEEORT

现在很容易判断你是否有四场或更多场比赛; 你只需运行最长公共子序列算法OPSTXZ,GINOPPST并发现最长的公共子序列OPST是四个字母,所以它匹配.最长公共子序列OPSTXZ和ADHOPRST也OPST,所以它maches.的最长公共子OPSTXY和GINOPT是OPT,这是只有三个,和的最长公共子OPSTXY和ACDEEORT是OT,这是只有两个.

假设这些单词都很短,我们就知道可以快速解决最长公共子序列问题和排序字符串问题.你只需要这样做4000万次,你就完成了.

现在,如果你想要一个次线性解决方案,在那里你可以尽早消除这些4000万个词汇中的一堆,那就更难了.您需要次线性解决方案吗？