最长共同后缀

我想找到两个字符串在斯卡拉最长的共同后缀。最长共同后缀

def longestSuffix(s1: String, s2: String) = { 
    val it = (s1.reverseIterator zip s2.reverseIterator) takeWhile {case (x, y) => x == y} 
    it.map (_._1).toList.reverse.mkString 
}

此代码笨拙，可能效率低下（例如因为反转）。如何找到功能最长的共同后缀，即没有可变变量？

来源

2017-03-09 Michael

一来改进它的方法是将连接反向和地图在最后一次操作：

str1.reverseIterator.zip(str2.reverseIterator).takeWhile(c => c._1 == c._2) 
.toList.reverseMap(c => c._1) mkString ""

首先做一个清单，然后reverseMap这个名单

来源

2017-03-09 11:39:29

我们可以遍历子，无反向：

def longestSuffix(s1: String, s2: String) = { 
    s1.substring(s1.length to 0 by -1 takeWhile { n => s2.endsWith(s1.substring(n)) } last) 
}

来源

2017-03-09 11:41:11

谢谢。有趣但有点复杂。 – Michael

让tails产生子字符串，然后返回适合的第一个字符串。

def longestSuffix(s1: String, s2: String) = 
    s1.tails.dropWhile(!s2.endsWith(_)).next

通过在两个输入中较短的一个上调用tails可以获得一些效率。

来源

2017-03-09 14:47:36 jwvh

谢谢。看起来不错，但恐怕是'O（N^2）' – Michael

我想出了这样一个解决方案：

def commonSuffix(s1: String, s2: String): String = { 
    val n = (s1.reverseIterator zip s2.reverseIterator) // mutable ! 
      .takeWhile {case (a, b) => a == b} 
      .size 
    s1.substring(s1.length - n) // is it efficient ? 
}

请注意，我用的substring效率（不知道这是否是正确的）。

这种解决方案，因为我使用reverseIterator尽管是可变的，因为我没有找到另一种方式来遍历以相反的顺序串也不是完全的“功能”。你会如何建议修复/改进它？

来源

2017-03-31 09:40:16 Michael

最长共同后缀

回答

相关问题