我只是在寻找一种具有最佳计算复杂度的高效算法来检查子字符串 - tobeVerified
是否存在于一个巨大的父字符串中
我经历了不同的算法,但我还没有找到提供 O(n) 的东西
我使用 HashSet
想出了下面的实现,它给了我 O(n+m) ~ O(n)
我想检查一下这是否是正确的做法,或者是否可以进行任何其他优化。但是这种方式存在占用空间较大的问题
String parent = "the value is very high";
String tobeVerified = "is";
Set wordSet = new HashSet<String>();
String[] words = parent.trim().toUpperCase().split("\\s+");
//This is O(n) n - Parent Size m - substring size
for(String word: words){
wordSet.add(word);
}
//This is O(1)
System.out.println(wordSet.contains(tobeVerified.toUpperCase()));
}
最佳答案
经典的 O(n+m)
子串搜索算法之一是 Boyer-Moore .对于足够大的字符串,它应该比 String.contains
或 String.indexOf
具有更好的性能。
在上面的维基百科页面链接上有该算法的 Java 实现,但它被编写为使用 char[]
数组作为输入,而不是在 String 类的实例上。因此,要么修改代码以使用 String 参数,要么考虑将 String
克隆到 char[]
的额外成本 O(n)。
我在维基百科代码中发现了一个小问题。它假定字符值仅在 8 位范围内。您可能需要修改此行:
final int ALPHABET_SIZE = 256;
变成这样:
final int ALPHABET_SIZE = 65536;
更新:我适本地更新了维基百科页面代码以获得正确的 ALPHABET_SIZE
值。确认存在原始错误并编写单元测试来验证修复。
关于java - 大字符串中的子字符串搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41647850/