的情况下，我有一个List<String>部分匹配字符串List.contains（字符串）
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")，我可以得到一个真实的吗？我的意思是，我可以部分匹配字符串来查找它们是否存在于列表中？
我有一个15000个字符串的列表。如果它们存在于列表中，我必须检查大约10000个字符串。什么可能是其他（更快）的方式来做到这一点？
谢谢。
也许你想把每个字符串组放入一个HashSet，并且通过片段，我的意思是不添加“IJ KL”，而是分别添加“IJ”和“KL”。如果您需要列表和此搜索功能，则可能需要维护两个集合。
+1是的，这是一种倒排索引。 – mschonaker
一种后缀数组。 – Heisenberg
您可以遍历该列表，然后在每个String上调用contains（）。
public boolean listContainsString(List<string> list. String checkStr)
{
Iterator<String> iter = list.iterator();
while(iter.hasNext())
{
String s = iter.next();
if (s.contain(checkStr))
{
return true;
}
}
return false;
}
这样的事情应该可以工作，我想。
这就是我现在正在做的事情。但如果我想部分匹配，这会给我一个错误。此外，我将不得不通过10000次遍历15000个条目。 – y2p
我不确定我是否理解这个问题。我很肯定，这将在部分匹配时按照您的要求返回true，尽管这里很晚，所以我可能完全错过了疲倦中的一个错误。另外，正如Hovercraft所建议的那样，你知道他们是否会在任何情况下被分开（与空间或其他角色）？如果是这样，那会让问题变得更容易。 –
作为第二个答案，在重读你的问题，你也可以从界面List继承，只专注它Strings，并覆盖包括（）方法。
public class PartialStringList extends ArrayList<String>
{
public boolean contains(Object o)
{
if(!(o instanceof String))
{
return false;
}
String s = (String)o;
Iterator<String> iter = iterator();
while(iter.hasNext())
{
String iStr = iter.next();
if (iStr.contain(s))
{
return true;
}
}
return false;
}
}
根据您之前的评论判断，这可能不是您想要的速度，但是这与您要求的速度更接近吗？
如何：
java.util.List<String> list = new java.util.ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");
java.util.regex.Pattern p = java.util.regex.Pattern.compile("IJ");
java.util.regex.Matcher m = p.matcher("");
for(String s : list)
{
m.reset(s);
if(m.find()) System.out.println("Partially Matched");
}
如果从走鹃-EX的建议不那么足够了，我相信你正在寻找Knuth–Morris–Pratt algorithm。
时间复杂度：
因此，整个算法的复杂度为O（n + k）。
普通蛮力将有时间复杂度O（nm）的
此外KMP算法将使用相同的搜索字符串进行搜索时具有相同的O（k）复杂度，但另一方面，对于蛮力方法，它总是O（km）。
O（nm）和O（km）中的m是多少？另外，请查看下面我简单的O（k）解决方案。为什么不行？ –
这里有一些代码使用正则表达式来快速内部循环如果无的测试字符串在目标字符串中找到。
public static void main(String[] args) throws Exception {
List<String> haystack = Arrays.asList(new String[] { "ABCD", "EFGH", "IJ KL", "M NOP", "UVW X" });
List<String> needles = Arrays.asList(new String[] { "IJ", "NOP" });
// To cut down on iterations, create one big regex to check the whole haystack
StringBuilder sb = new StringBuilder();
sb.append(".*(");
for (String needle : needles) {
sb.append(needle).append('|');
}
sb.replace(sb.length() - 1, sb.length(), ").*");
String regex = sb.toString();
for (String target : haystack) {
if (!target.matches(regex)) {
System.out.println("Skipping " + target);
continue;
}
for (String needle : needles) {
if (target.contains(needle)) {
System.out.println(target + " contains " + needle);
}
}
}
}
输出：
Skipping ABCD
Skipping EFGH
IJ KL contains IJ
M NOP contains NOP
Skipping UVW X
如果你真的想要得到可爱的，你可以平分使用二进制搜索，以确定该目标列表的匹配段，但它可能不值得。
这取决于它是多么可能yo'll发现一个打击。低命中率会带来好的结果。高命中率的表现并不比简单的嵌套循环版本更好。如果一些针头击中多个目标，则考虑倒置环路，其他击中任何一个。
这是所有关于尽快中止搜索路径。
对于初学者来说，对上帝的爱，请使用一组（例如，HashSet的），而不是一个列表。在列表中做一个contains（）是O（n），但是在一个集合上它是O（1）。只需要很小的修复就可以为您节省大量时间。
现在，插入你的项目一个接一个，包括对词分裂他们。例如：
java.util.Set<String> set = new java.util.HashSet<String>();
set.add("ABCD");
set.add("IJ");
set.add("IJ KL");
，如果你想在字符串的中间部分匹配的话（不只是开头），地址：
set.add("KL");
退房String.split（）来快速拆分文本基于空间。
现在，当你搜索，你可以这样做：
boolean isItThere = set.contains("IJ");
田田！非常简单的O（1）搜索。这将会非常快。注意：假设每个条目有10个字符，平均每个条目有2个字的10,000个条目，这意味着我们在这里使用< 200k的内存（10k * 10 * 2 = 200k）。如果你的字符串大小增加，或者你的字数增加，这可能会匆匆失控。那么你应该看看像Lucene。
是的，你可以！有点。
你所寻找的，通常被称为fuzzy searching or approximate string matching有几种解决问题的对策。
随着FuzzyWuzzy LIB，例如，你可以指定分数您的所有字符串基础上，他们是一个特定的搜索词多么的相似。实际值似乎是与搜索字符串长度匹配的字符数的整数百分比。
调用FuzzySearch.extractAll后，它是由你来决定的最低分数会是怎样的一个字符串被认为是匹配的。
还有其他类似的库值得检查，如google-diff-match-patch或Apache Commons Text Similarity API等等。
如果你需要一些真正的重型，你最好的选择很可能是Lucene（如也Ryan Shillington提到）
你可以使用IterableUtils从Apache Commons Collections。
List<String> list = new ArrayList<String>();
list.add("ABCD");
list.add("EFGH");
list.add("IJ KL");
list.add("M NOP");
list.add("UVW X");
boolean hasString = IterableUtils.contains(list, "IJ", new Equator<String>() {
@Override
public boolean equate(String o1, String o2) {
return o2.contains(o1);
}
@Override
public int hash(String o) {
return o.hashCode();
}
});
System.out.println(hasString); // true
* “我能得到'list.contains的情况下，'真'（” IJ “）'？” *发生了什么事，当你试过* *呢？ –
返回'false' – y2p
你必须知道*它匹配的是哪一个确切的*项，还是足以知道它与你的一个术语相匹配（不知道哪一个）？ – Bohemian