如何在Scala中找到两个字符串之间的最大重叠? [英] How to find maximum overlap between two strings in Scala?

问题描述

假设我有两个字符串:s 和 t.我需要编写一个函数 f 来找到最大值.t 前缀，也是一个 s 后缀.例如:

Suppose I have two strings: s and t. I need to write a function f to find a max. t prefix, which is also an s suffix. For example:

 s = "abcxyz", t = "xyz123", f(s, t) = "xyz"
 s = "abcxxx", t = "xx1234", f(s, t) = "xx"

你会如何在 Scala 中编写它?

How would you write it in Scala ?

推荐答案

第一个解决方案是最简洁的，而且比递归版本更有效，因为它使用了延迟评估的迭代

This first solution is easily the most concise, also it's more efficient than a recursive version as it's using a lazily evaluated iteration

s.tails.find(t.startsWith).get

现在有一些关于 tails 是否会一遍又一遍地复制整个字符串的讨论.在这种情况下，您可以在 s 上使用 toList 然后 mkString 结果.

Now there has been some discussion regarding whether tails would end up copying the whole string over and over. In which case you could use toList on s then mkString the result.

s.toList.tails.find(t.startsWith(_: List[Char])).get.mkString

出于某种原因，需要类型注释才能编译它.我实际上并没有尝试查看哪个更快.

For some reason the type annotation is required to get it to compile. I've not actually trying seeing which one is faster.

更新 - 优化

正如 som-snytt 所指出的，t 不能以任何比它长的字符串开头，因此我们可以进行以下优化:

As som-snytt pointed out, t cannot start with any string that is longer than it, and therefore we could make the following optimization:

s.drop(s.length - t.length).tails.find(t.startsWith).get

这篇关于如何在Scala中找到两个字符串之间的最大重叠?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！