高效的字符串匹配算法

Question

我正在尝试建立一种有效的字符串匹配算法。这将在大容量环境中执行，因此性能至关重要。

这是我的要求：

• 给定一个域名，即www.example.com，确定它是否与条目列表中的一个“匹配”。
• 条目可能是绝对匹配项，即www.example.com。
• 条目可能包含通配符，即* .example.com。
• 通配符条目从最定义的级别开始向上匹配。例如，*。example.com将与www.example.com，example.com和sub.www.example.com匹配。
• 通配符条目未嵌入，即sub。*。example.com将不是条目。

语言/环境：C＃（.Net Framework 3.5）

我考虑过将条目（和域查找）拆分为数组，颠倒顺序，然后遍历数组。虽然准确，但感觉很慢。

我考虑过正则表达式，但担心将条目列表准确地表示为正则表达式。

我的问题：给定上面列出的说明，一种有效的方式来查找域名形式的字符串是否与字符串列表中的任何一个匹配？

Answer 1

如果您想自己动手，我会将条目存储在树形结构中。

而不是通过“”标记该结构。字符，我只会将每个条目视为完整字符串。任何标记化的实现仍然仍然必须对整个字符集进行字符串匹配，因此您也可以一次性完成所有操作。

它和常规拼写检查树之间的唯一区别是：

1. 匹配需要反向进行
2. 您必须考虑通配符

要解决第2点，您只需在测试结束时检查“ *”字符。

一个简单的例子：

参赛作品：

*.fark.com
www.cnn.com

树：

m -> o -> c -> . -> k -> r -> a -> f -> . -> *
                \
                 -> n -> n -> c -> . -> w -> w -> w

检查www.blog.fark.com将涉及到从树到第一个树的跟踪"*"。由于遍历以结束"*"，因此存在匹配项。

检查www.cern.com将在n，n，c，…的第二个“ n”上失败。

由于遍历以以外的其他字符结束，因此检查dev.www.cnn.com也会失败"*"。