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

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;
}

}

Answer 1

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