3

我有一组大小约为 100-200 的元素。设一个样本元素为X。

每个元素都是一组字符串（这样的集合中的字符串数在 1 到 4 之间）。X= { s1, s2, s3}

对于给定的输入字符串（大约 100 个字符），例如P，我想测试字符串中是否X存在任何。

X存在于iff 中，表示所有属于，是的子串。PsXsP

该组元素可用于预处理。

我希望这在 Java 中尽可能快。不符合我要求的可能方法：

  • 检查所有字符串是否s都是子字符串P似乎是一项代价高昂的操作
  • 因为s可以是P（不一定是单词）的任何子字符串，所以我不能使用单词的散列
  • 我不能直接使用正则表达式，因为s1, s2,s3可以以任何顺序出现，并且所有字符串都需要作为子字符串出现

现在我的方法是X用所有可能的字符串顺序排列构建一个巨大的正则表达式。因为 <= 4 中的元素数量X，这仍然是可行的。如果有人可以为我指出一种更好（更快/更优雅）的方法，那就太好了。

请注意，这组元素可用于预处理，我想要 java 中的解决方案。

4

7 回答 7

2

您可以直接使用正则表达式：

Pattern regex = Pattern.compile(
    "^               # Anchor search to start of string\n" +
    "(?=.*s1)        # Check if string contains s1\n" +
    "(?=.*s2)        # Check if string contains s2\n" +
    "(?=.*s3)        # Check if string contains s3", 
    Pattern.DOTALL | Pattern.COMMENTS);
Matcher regexMatcher = regex.matcher(subjectString);
foundMatch = regexMatcher.find();

foundMatch如果字符串中存在所有三个子字符串，则为真。

请注意，如果“针字符串”可能包含正则表达式元字符，您可能需要转义它们。

于 2012-09-11T09:50:40.337 回答
1

看起来像是Rabin–Karp 算法的完美案例：

Rabin-Karp 在单模式搜索方面不如 Knuth-Morris-Pratt 算法、Boyer-Moore 字符串搜索算法和其他更快的单模式字符串搜索算法，因为它的最坏情况行为较慢。然而，Rabin-Karp 是多模式搜索的首选算法。

于 2013-04-28T03:27:58.643 回答
1

听起来您在实际发现特定方法实际上太慢之前就过早地优化了代码。

关于你的字符串集的一个很好的属性是字符串必须包含X作为子字符串的所有元素——这意味着如果我们发现其中一个元素X不包含在其中，我们可能会很快失败P。这可能会比其他方法更节省时间，特别是如果 的元素X通常比几个字符长并且不包含或只包含几个重复字符。例如，正则表达式引擎在检查是否存在具有非重复字符的 5 长度字符串（例如海岸）时，只需要检查 100 长度字符串中的 20 个字符。而且由于X有 100-200 个元素，如果可以的话，你真的非常想快速失败。

我的建议是按长度顺序对字符串进行排序，然后依次检查每个字符串，如果找不到一个字符串，请尽早停止。

于 2012-09-11T10:52:01.540 回答
0

One way is to generate every possible substring and add this to a set. This is pretty inefficient.

Instead you can create all the strings from any point to the end into a NavigableSet and search for the closest match. If the closest match starts with the string you are looking for, you have a substring match.

static class SubstringMatcher {
    final NavigableSet<String> set = new TreeSet<String>();

    SubstringMatcher(Set<String> strings) {
        for (String string : strings) {
            for (int i = 0; i < string.length(); i++)
                set.add(string.substring(i));
        }
        // remove duplicates.
        String last = "";
        for (String string : set.toArray(new String[set.size()])) {
            if (string.startsWith(last))
                set.remove(last);
            last = string;
        }
    }

    public boolean findIn(String s) {
        String s1 = set.ceiling(s);
        return s1 != null && s1.startsWith(s);
    }
}

public static void main(String... args) {
    Set<String> strings = new HashSet<String>();
    strings.add("hello");
    strings.add("there");
    strings.add("old");
    strings.add("world");
    SubstringMatcher sm = new SubstringMatcher(strings);
    System.out.println(sm.set);
    for (String s : "ell,he,ow,lol".split(","))
        System.out.println(s + ": " + sm.findIn(s));
}

prints

[d, ello, ere, hello, here, ld, llo, lo, old, orld, re, rld, there, world]
ell: true
he: true
ow: false
lol: false
于 2012-09-11T10:39:40.903 回答
0

您可能正在寻找Aho-Corasick 算法，该算法从字符串集（字典）构造一个自动机（类 trie），并尝试使用此自动机将输入字符串与字典匹配。

于 2012-09-11T10:18:59.973 回答
0

当预处理时间无关紧要时，您可以创建一个哈希表，它将至少出现在一个字符串中的每个一个字母、两个字母、三个字母等组合映射到它出现的字符串列表。

索引字符串的算法如下所示（未经测试）：

HashMap<String, Set<String>> indexes = new HashMap<String, Set<String>>();

for (int pos = 0; pos < string.length(); pos++) {
    for (int sublen=0; sublen < string.length-pos; sublen++) {
         String substring = string.substr(pos, sublen);
         Set<String> stringsForThisKey = indexes.get(substring);
         if (stringsForThisKey == null) {
             stringsForThisKey = new HashSet<String>();
             indexes.put(substring, stringsForThisKey);
         }
         stringsForThisKey.add(string);
    }
}

以这种方式索引每个字符串将是字符串长度的二次方，但只需要对每个字符串执行一次。

但结果将是对出现特定字符串的字符串列表的恒定速度访问。

于 2012-09-11T10:02:19.187 回答
0

您可能还想考虑使用“后缀树”。我没有使用过这段代码，但是这里有一个描述

我使用了专有实现（我什至无法访问）并且它们非常快。

于 2012-09-11T11:22:20.523 回答