java - 在字符串中搜索未知模式的最有效方法？

Question

我正在尝试寻找以下模式:

• 出现不止一次
• 长度超过 1 个字符
• 不是任何其他已知模式的子串

不知道可能发生的任何模式。

例如:

• 字符串“the boy fall by the bell”将返回 'ell', 'the b', 'y '。
• 字符串“the boy fall by the bell, the boy fall by the bell”将返回'the boy fall by the bell'。

使用双 for 循环，可以非常低效地强制执行:

ArrayList<String> patternsList = new ArrayList<>();
int length = string.length();
for (int i = 0; i < length; i++) {
    int limit = (length - i) / 2;
    for (int j = limit; j >= 1; j--) {
        int candidateEndIndex = i + j;
        String candidate = string.substring(i, candidateEndIndex);

        if(candidate.length() <= 1) {
            continue;
        }

        if (string.substring(candidateEndIndex).contains(candidate)) {
            boolean notASubpattern = true;
            for (String pattern : patternsList) {
                if (pattern.contains(candidate)) {
                    notASubpattern = false;
                    break;
                }
            }

            if (notASubpattern) {
                patternsList.add(candidate);
            }
        }
    }
}

但是，在搜索具有大量模式的大型字符串时，这会非常慢。

Answer 1

您可以在线性时间内为您的字符串构建一个后缀树: https://en.wikipedia.org/wiki/Suffix_tree

您正在寻找的模式是与只有叶子 child 的内部节点对应的字符串。