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

Question

假设我有字符串"Torcellite"和另一个字符串"Tor" - 这两个字符串的相似长度是3,因为它们都以"Tor"开头.现在另一个字符串"christmas"和"mas"的相似度为0,因为它们不是以相同的字符集开头的.

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

一个更清晰的例子:

字符串长度:1到10 ^ 5

串: abaabc

后缀:abaabc,baabc,aabc,abc,bc,c

相似度:abaabc,无,a,ab,无,无

相似度长度: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)然后找到最长的组匹配.

是否有更高效的算法可以实现他的？

Answer 1

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

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

所以最终的结果是你可以在保证O(n) 时间和 O(n) 空间内解决问题，并且预处理时间为 O(n)。这相当有效！而且，不存在产生二次行为的“最坏情况”。这样您就可以轻松处理长度达 10^7 的字符串。

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