批处理字符串包含操作优化？

Question

我有2组字符串，A和B. 我想解决的问题是计算集B中有多少个字符串包含集合A中的任何单个字符串。例如：
答：“a”，“b “
B： ”ABC“， ”DSF“， ”AQC“， ”YYY“， ”XXX“， ”BBB“
结果为3（” ABC”， “AQC”， “BBB”）

不幸的是，集合A和集合B在我的情况下非常大，例如，集合A有数百万个字符串，集合B有数十亿个字符串。所以我必须在Java语言中采用数十亿的'indexof'操作。该算法的复杂度为O（m * n）。

是否有任何优化算法可以用来使其更快？

Answer 1

可能是数据库搜索和茶歇是常见的做法。

但让我们来看看。

使用套封：

• 地图每一封信给总理，最常见的字母第一：E 2，T 3，O 5，I 7，...
• 计算所有的产品A和B中的字符串的字母素数。
• 现在B中的候选人可以通过A中的任何元素进行分割。
• 这可能会减少很大因素的可能候选人的映射。

使用的搜索模式（在一个方面的字母树）：

• 这是一个有点像制作正则表达式 “（A | B）” 但后来非常大的。这种模式可以编译并针对每个单词运行。不确定这是否加速。

，进而使用Java 8与其并行数据流，在1000块从A和100​​0从B.