22

我正在尝试创建一个程序，以尽可能快地检测字符串中是否有多个单词，如果是，则执行一个行为。最好，我也希望它能够检测这些单词的顺序，但前提是这可以快速完成。到目前为止，这就是我所做的：

if (input.contains("adsf") && input.contains("qwer")) {
    execute();          
}

如您所见，对多个单词执行此操作会变得很烦人。这是检测多个子字符串的唯一方法还是有更好的方法？有什么方法可以检测顺序吗？

4

7 回答 7

38

我会从以下单词创建一个正则表达式：

Pattern pattern = Pattern.compile("(?=.*adsf)(?=.*qwer)");
if (pattern.matcher(input).find()) {
    execute();
}

有关更多详细信息，请参阅此答案：https ://stackoverflow.com/a/470602/660143

于 2013-09-19T01:51:04.367 回答
17

编者注：尽管被大力支持和接受，但它的功能与问题中的代码不同。execute在第一次匹配时调用，如逻辑 OR。

你可以使用一个数组：

String[] matches = new String[] {"adsf", "qwer"};

bool found = false;
for (String s : matches)
{
  if (input.contains(s))
  {
    execute();
    break;
  }
}

这与您发布的一样有效，但更易于维护。寻找一个更有效的解决方案听起来像是一个微优化，在被证明是你的代码的有效瓶颈之前应该忽略它，在任何情况下，如果有一个巨大的字符串集，这个解决方案可能是一个尝试。

于 2013-09-19T01:49:49.750 回答
11

在 Java 8 中你可以做

public static boolean containsWords(String input, String[] words) {
    return Arrays.stream(words).allMatch(input::contains);
}

示例用法：

String input = "hello, world!";
String[] words = {"hello", "world"};
if (containsWords(input, words)) System.out.println("Match");
于 2018-06-24T08:27:35.513 回答
1

如果您有很多子字符串要查找，那么正则表达式可能不会有太大帮助，因此您最好将子字符串放在一个列表中，然后遍历它们并调用input.indexOf(substring)每个子字符串。这将返回int找到子字符串的位置的索引。如果您将每个结果（-1 除外，这意味着未找到子字符串）放入 a TreeMap（其中是键，子字符串是值），那么您可以通过调用mapindex来按顺序检索它们。keys()

Map<Integer, String> substringIndices = new TreeMap<Integer, String>();
List<String> substrings = new ArrayList<String>();
substrings.add("asdf");
// etc.

for (String substring : substrings) {
  int index = input.indexOf(substring);

  if (index != -1) {
    substringIndices.put(index, substring);
  }
}

for (Integer index : substringIndices.keys()) {
  System.out.println(substringIndices.get(index));
}
于 2013-09-19T01:53:21.763 回答
1

使用树结构来保存每个代码点的子字符串。这消除了需要

请注意，这只有在针组几乎恒定时才有效。虽然单独添加或删除子字符串并不是低效的，但是每次将大量字符串排列成树结构的不同初始化肯定会减慢它。

StringSearcher：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

class StringSearcher{
    private NeedleTree needles = new NeedleTree(-1);
    private boolean caseSensitive;
    private List<Integer> lengths = new ArrayList<>();
    private int maxLength;

    public StringSearcher(List<String> inputs, boolean caseSensitive){
        this.caseSensitive = caseSensitive;
        for(String input : inputs){
            if(!lengths.contains(input.length())){
                lengths.add(input.length());
            }
            NeedleTree tree = needles;
            for(int i = 0; i < input.length(); i++){
                tree = tree.child(caseSensitive ? input.codePointat(i) : Character.toLowerCase(input.codePointAt(i)));
            }
            tree.markSelfSet();
        }
        maxLength = Collections.max(legnths);
    }

    public boolean matches(String haystack){
        if(!caseSensitive){
            haystack = haystack.toLowerCase();
        }
        for(int i = 0; i < haystack.length(); i++){
            String substring = haystack.substring(i, i + maxLength); // maybe we can even skip this and use from haystack directly?
            NeedleTree tree = needles;
            for(int j = 0; j < substring.maxLength; j++){
                tree = tree.childOrNull(substring.codePointAt(j));
                if(tree == null){
                    break;
                }
                if(tree.isSelfSet()){
                    return true;
                }
            }
        }
        return false;
    }
}

NeedleTree.java：

import java.util.HashMap;
import java.util.Map;

class NeedleTree{
    private int codePoint;
    private boolean selfSet;
    private Map<Integer, NeedleTree> children = new HashMap<>();

    public NeedleTree(int codePoint){
        this.codePoint = codePoint;
    }

    public NeedleTree childOrNull(int codePoint){
        return children.get(codePoint);
    }

    public NeedleTree child(int codePoint){
        NeedleTree child = children.get(codePoint);
        if(child == null){
            child = children.put(codePoint, new NeedleTree(codePoint));
        }
        return child;
    }

    public boolean isSelfSet(){
        return selfSet;
    }

    public void markSelfSet(){
        selfSet = true;
    }
}
于 2016-07-24T06:03:39.397 回答
1

这是一个经典的面试和 CS 问题。

Robin Karp 算法通常是人们在采访中首先谈论的内容。基本思想是，在遍历字符串时，将当前字符添加到散列中。如果哈希与您的一个匹配字符串的哈希匹配，则您知道您可能有一个匹配项。这避免了在匹配字符串中来回扫描。 https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

该面试问题的其他典型主题是考虑使用 trie 结构来加快查找速度。如果您有大量匹配字符串，则必须始终检查大量匹配字符串。trie 结构更有效地进行检查。 https://en.wikipedia.org/wiki/Trie

其他算法是： - Aho–Corasick https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm - Commentz-Walter https://en.wikipedia.org/wiki/Commentz-Walter_algorithm

于 2019-03-01T14:14:19.350 回答
-1

我认为更好的方法是这样的，我们可以将多个值添加为一个字符串，并通过函数的索引验证索引

String s = "123"; 
System.out.println(s.indexOf("1")); // 0
System.out.println(s.indexOf("2")); // 1 
System.out.println(s.indexOf("5")); // -1
于 2019-04-11T11:40:02.350 回答