在List.contains（String）的情况下部分匹配字符串 [英] Partially match strings in case of List.contains(String)

问题描述

我有列表< String>

List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");

如果我 list.contains（EFGH），它返回 true 。
如果 list.contains（IJ），我能获得真实吗？我的意思是，我可以部分匹配字符串以查找它们是否存在于列表中吗？

if I do list.contains("EFGH"), it returns true. Can I get a true in case of list.contains("IJ")? I mean, can I partially match strings to find if they exist in the list?

我有一个包含15000个字符串的列表。如果它们存在于列表中，我必须检查大约10000个字符串。有什么其他（更快）的方法可以做到这一点？

I have a list of 15000 strings. And I have to check about 10000 strings if they exist in the list. What could be some other (faster) way to do this?

谢谢。

推荐答案

如果Roadrunner-EX的建议不够，我相信你正在寻找 Knuth-Morris-Pratt算法。

If suggestion from Roadrunner-EX does not suffice then, I believe you are looking for Knuth–Morris–Pratt algorithm.

时间复杂度：

• 表算法的时间复杂度为O（n），预处理时间


• 搜索算法的时间复杂度为O（k）

因此，整体算法的复杂性为O（n + k）。

So, the complexity of the overall algorithm is O(n + k).

• n =列表大小


• k =您要搜索的模式长度

普通Brute-Force的时间复杂度为O（nm）

Normal Brute-Force will have time complexity of O(nm)

此外，KMP算法在搜索相同搜索时会采用相同的O（k）复杂度另一方面，对于暴力攻击，它总是O（km） ach。

Moreover KMP algorithm will take same O(k) complexity for searching with same search string, on the other hand, it will be always O(km) for brute force approach.

这篇关于在List.contains（String）的情况下部分匹配字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！