java - 大字符串中的子字符串搜索算法

Question

我只是在寻找一种具有最佳计算复杂度的高效算法来检查子字符串 - 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()));
    }

Answer 1

经典的 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 值。确认存在原始错误并编写单元测试来验证修复。