最も長い共通接尾辞

Question

私はScalaで2つの文字列の最も長い共通接尾辞を見つけたいと思います。

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 
} 

このコードは不器用で、おそらく非効率です（たとえば、逆転のため）。どのようにして最も長い共通の接尾辞が機能的に、つまり可変変数なしで見つかるでしょうか？それを改善するために

Answer 1

一つの方法は、逆に接続し、最後の操作にマッピングするために、次のようになります。

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

は、まず、リストを作成し、その後、reverseMapこのリスト

Answer 2

は、我々は逆ずに、部分文字列を反復処理することができます。

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

Answer 3

tailsは、サブ文字列を生成してみましょう、その後収まる最初のを返します。

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

2つの入力のうち短いほうにtailsを呼び出すと、効率が上がる場合があります。

Answer 4

私はこのような解決策を思い付いた：私は効率のためにsubstringを使用しています

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 ? 
}

注意（それが正しいかどうかわかりません）。

私はreverseIteratorを使用していますので、このソリューションは、私が逆の順序で文字列を反復する別の方法を見つけられませんでしたので、それは変更可能ですにもかかわらず、完全に「機能的」ではありません。あなたはそれを修正/改善することをどのように示唆しますか？