部分匹配长度的正则表达式 - 字符串相似性

string regex java pattern-matching

2022-09-04 04:16:18

假设我有字符串“Torcellite”和另一个字符串“Tor” - 这两个字符串的相似性长度为3，因为它们都以“Tor”开头。现在，另一个字符串“christmas”和“mas”的相似性将为0，因为它们不以相同的字符集开头。

在这两种情况下，第二个字符串都是第一个字符串的后缀。

一个更清晰的例子：

字符串长度：1 到 10^5

字符串：abaabc

后缀：abaabcbaabcaabcabcbcc

相似性：、无、、、无、无abaabcaab

相似性长度： 6， 0， 1， 2， 0， 0

答案： 6+0+1+2+0+0 = 9

我有一个低效的逻辑来使用正则表达式找到这些部分后缀匹配项。

算法：

查找给定字符串的所有子字符串。

从后缀的子字符串创建模式。

for(int i=1; i<substrings[i].length; i++) {
    Pattern p = Pattern.compile("^"+substrings[i].substring(0, i));
    Matcher m = p.find(string); //the given string for which similarities need to be  calculated
    if(m.find())
        similaryLengths +=  i;
}

这样做的复杂性大约变成了O（n^2），因为我需要遍历字符串的后缀，然后是模式的子字符串。
我已经想到在模式中使用分组来查找组，但我不确定正则表达式会是什么样子。我想到的第一个子字符串是：然后找到最长的组匹配。((((((a)b)a)a)b)c)

有没有更有效的算法可以实现他的？

答案 1

到目前为止，最好的方法是在输入字符串上构建后缀树。生成后缀树只需要 O（n）时间，其中 n 是字符串的长度。后缀树在逻辑上由一棵树组成，其中字符串的所有后缀都可以通过从根走到每个叶子来找到。您可以阅读维基百科，了解有关这些树如何工作的更多详细信息。

从本质上讲，后缀树将允许您简单地将当前问题重铸为在后缀树中“查找”原始字符串的问题之一。当您沿着树向下走时，您可以计算每个子树中的后缀数量，然后乘以当前匹配长度以确定您的分数。这种“搜索”也需要O（n）时间。

所以最终的结果是，你可以用O（n）预处理时间在保证的O（n）时间和O（n）空间中解决问题。这是非常有效的！而且，没有产生二次行为的“最坏情况”。有了这个，您可以轻松处理长度高达10 ^ 7的字符串。

实现中唯一的困难是构建后缀树，但您可以找到免费提供的代码。

答案 2

Simliar算法已经由Valdar Moridin发布，但不需要创建子字符串（每次调用都会创建一个新对象，其中包含其源的指定范围的副本）。这不会提高时间复杂性，但可能会减少常量因子的总运行时间：substringStringchar[]

public static int partialSuffixMatch(CharSequence input) {
    int count = input.length();
    for (int i = 1; i < input.length(); i++) {
        for (int a = 0, b = i; b < input.length(); a++, b++) {
            if (input.charAt(a) != input.charAt(b))
                break;
            count++;
        }
    }
    return count;
}

经过短暂的预热后，此算法在我的计算机上大约40毫秒内处理具有10，000个相等字符的a，并在大约4秒内处理100，000个相等字符。String