java - 使用线程计算子字符串的所有出现次数

Question

假设我有 t 个线程，计算字符串 S 中子字符串 T 的所有非重叠出现的最佳解决方案是什么？

这是一段正常计数的代码，但我不确定如何同时实现它。如果 t 小于子串的长度会发生什么？

public class Substrings {
public int countOccurrences(String S, String T) {
  int count = 0, offset = 0, index;
  while((index = S.indexOf(T, offset)) != -1) {
    offset = index + T.length();
            count++;
  }
  return count;
}

}

标签： javamultithreadingconcurrency

Answer 1

我不确定你为什么要这样做，因为这样的操作非常快，除非你有很多巨大的字符串。最佳解决方案不是我想考虑的，但是有一种简单的方法可以做到这一点，它的速度大约是最佳解决方案的两倍。将字符串拆分为多个部分，并使用线程在每个部分上运行 countOccurrences。将您找到的所有索引放入一个集合中。然后将这些部分向前滑动一段长度的一半，然后再做一次。第二部分将查找跨节的任何事件。当然，您可以通过两侧字符串的长度来限制第二次搜索，但这会使代码复杂化。作为一个练习，也许你可以用 Boyer-Moore 来做这个。