java - 检查干草堆是否包含针组的最快方法

我有一根干草堆绳子，我想看看里面有没有针线。目前我是这样做的：

Set<String> needles = ...;

...

String [] pieces = haystack.split(" ");
for (String piece: pieces) {
  if (needles.contains(piece) {
    return true;
  }
}

return false;

它起作用，但速度相对较慢。
问：有没有更快的方法来完成这项任务？
例子。

 Haystack: I am a big tasty potato .
 Needles:  big, tasty

 == RUN ==
 I am a big tasty potato .
        |
        [tasty] got a match, we are good!

最佳答案

你应该看看Aho-Corasick算法。这适合您的问题，因为它构建了一个所有单词（针）的自动机，并在构建的自动机上遍历文本（草堆）以找到所有匹配的单词。它基本上构造了一个类似trie的有限状态机。
时间复杂度O(n + m + z)
z是文本中单词出现的总数，n是文本的长度，m是所有单词中字符的总数。
编辑2
这里是一个直接的实现，它在发现任何针的第一次出现后停止遍历。

import java.util.*;

class AhoCorasick {

  static final int ALPHABET_SIZE = 256;

  Node[] nodes;
  int nodeCount;

  public static class Node {
    int parent;
    char charFromParent;
    int suffLink = -1;
    int[] children = new int[ALPHABET_SIZE];
    int[] transitions = new int[ALPHABET_SIZE];
    boolean leaf;

    {
      Arrays.fill(children, -1);
      Arrays.fill(transitions, -1);
    }
  }

  public AhoCorasick(int maxNodes) {
    nodes = new Node[maxNodes];
    // create root
    nodes[0] = new Node();
    nodes[0].suffLink = 0;
    nodes[0].parent = -1;
    nodeCount = 1;
  }

  public void addString(String s) {
    int cur = 0;
    for (char ch : s.toCharArray()) {
      int c = ch;
      if (nodes[cur].children[c] == -1) {
        nodes[nodeCount] = new Node();
        nodes[nodeCount].parent = cur;
        nodes[nodeCount].charFromParent = ch;
        nodes[cur].children[c] = nodeCount++;
      }
      cur = nodes[cur].children[c];
    }
    nodes[cur].leaf = true;
  }

  public int suffLink(int nodeIndex) {
    Node node = nodes[nodeIndex];
    if (node.suffLink == -1)
      node.suffLink = node.parent == 0 ? 0 : transition(suffLink(node.parent), node.charFromParent);
    return node.suffLink;
  }

  public int transition(int nodeIndex, char ch) {
    int c = ch;
    Node node = nodes[nodeIndex];
    if (node.transitions[c] == -1)
      node.transitions[c] = node.children[c] != -1 ? node.children[c] : (nodeIndex == 0 ? 0 : transition(suffLink(nodeIndex), ch));
    return node.transitions[c];
  }

  // Usage example
  public static void main(String[] args) {
    AhoCorasick ahoCorasick = new AhoCorasick(1000);
    ahoCorasick.addString("big");
    ahoCorasick.addString("tasty");

    String s = "I am a big tasty potato";
    int node = 0;
    for (int i = 0; i < s.length(); i++) {
      node = ahoCorasick.transition(node, s.charAt(i));
      if (ahoCorasick.nodes[node].leaf) {
        System.out.println("A match found! Needle ends at: " + i); // A match found! Needle ends at: 9
        break;
      }
    }
  }
}

但是，当前此代码将找到文本中任何匹配项的结束位置如果你需要起始位置和/或针，你可以从结束位置追溯到找到一个空间来得到匹配的单词。
在最坏的情况下，这并不能保证速度，但在平均和最佳的情况下应该会更好。

关于java - 检查干草堆是否包含针组的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39935132/