string - 逐字 super 字符串搜索给定字符串

Question

对于任何输入的字符串，我们需要按任意顺序的单词匹配来查找 super 字符串。即输入字符串中的所有单词必须以任何顺序出现在输出字符串中。例如给定数据集:“字符串搜索”“Java 字符串搜索”“手动 C 字符串搜索等于”“java搜索代码”“c java代码搜索”...

输入:“java搜索”输出:1)“java字符串搜索”2)“java搜索代码”3)“c java代码搜索”

输入:“搜索c”输出:1) “手动 c 字符串搜索等于”2)“c java代码搜索”

这可以通过逐字匹配以非常简单的方式完成。在这里，我主要是在寻找一种高效的算法。

输入:给定数据集中的数十亿条记录(主要是 1 到 10 个字长的字符串)。我需要为数百万个字符串找到 super 字符串。注:词是扩展字典词。

Answer 1

预处理您的输入(如果可能)，并对出现在数据集中的单词编制索引。生成从每个单词到一组可能的输出字符串的映射。例如，数据集

0 string search
1 java string search
2 manual c string search equals
3 java search code
4 c java code search

我们得到

c {2,4}
code {3,4}
equals {2}
java {1,3,4}
...

然后，搜索给定输入的匹配项就像将与输入词对应的集合相交一样简单:

input: "java c"
output: {1,3,4} intersect {2,4} = {4}

如果您将集合存储为有序列表，则可以通过并行扫描列表在线性时间内(与输入集合的总长度成线性关系)完成交集。