在C#中匹配两大字符串

Question

情况如下:

我有一个网页,我已经作为一个字符串刮.

我在MSSQL数据库中有几个字段.例如,汽车模型,它有一个ID和一个名称,如Mustang或Civic.它预装了大多数车型.

我想找到我的模型表中任何行的任何匹配项.因此,如果我在我的模型表中有思域,野马和E350,我想在我抓过的页面上找到任何三个中的任何一个.

在C#中执行此操作的有效方法是什么？我正在使用LINQ to SQL与db进行交互.

创建所有模型的字典,标记页面和迭代标记是否有意义？或者我应该迭代标记并使用WHERE子句并询问数据库是否匹配？

    //Dictionary dic contains all models from the DB, with the name being the key and the id being the value...
    foreach(string pageToken in pageTokens)
    {
         if(dic.ContainsKey(pageToken)) 
         {
              //Do what I need to do
         }
    }

这两种方法对我来说都很糟糕.关于我应该做什么的任何建议？设想交叉的东西,我想可能会很好吗？

这些方法都没有解决当模型名称多于一个单词时发生的情况.如"F150 Extended Cab".对此的想法？

Answer 1

在较大的文本中搜索多个字符串是一个众所周知的问题,并且已经进行了大量研究以使其快速化.两种最流行和最有效的方法是Aho-Corasick算法(我推荐这个)和Rabin-Karp算法.他们使用了一些预处理,但是比Naieve方法复杂度更低且速度更快(naieve方法是最坏情况O(m*n ^ 2*p)其中m是长字符串的长度[网页你刮削]和n是针的平均长度,p是针的数量.Aho-Corsaik是线性的.AC#的实现可以在CodeProject免费找到.

编辑:哎呀,我错了Aho-Corasick的复杂性 - 它在输入字符串的数量和长度上是线性的+正在分析的字符串的大小[刮下的文本]加上匹配的数量.但它仍然是线性的,线性比立方体好很多:-).