时间戳

首页 > 解决方案 > 在字符串中查找短语的更有效方法？

algorithm - 在字符串中查找短语的更有效方法？

问题描述

我有一个包含 100,000 多个按长度排序的单词/短语的列表

let list = [“string with spaces”, “another string”, “test”, ...]

我需要在上面的列表中找到给定句子中最长的元素。这是我最初的解决方案

for item in list {
    if sentence == item
        || sentence.startsWith(item + “ “) 
        || sentence.contains(“ “ + item + “ “) 
        || sentence.endsWith(“ “ + item) {
        ...
        break
    }
}

我遇到的这个问题是这对我的应用程序来说太慢了。我可以采取不同的方法来加快速度吗？

标签： algorithm

解决方案

您可以从列表中构建一个 Aho-Corasick 搜索器，然后在句子上运行它。根据https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm “算法的复杂性在字符串长度加上搜索文本的长度加上输出匹配的数量是线性的。注意因为找到了所有匹配项，所以如果每个子字符串都匹配（例如字典 = a、aa、aaa、aaaa 和输入字符串是 aaaa），则可能有二次匹配数。"

推荐阅读