Elixir 找到字符串中最长的子串

Elixir find the longest substring in a string

我的问题和Find the longest substring in a string

一模一样

但与丹药有关

我目前的实现非常丑陋:

str = "aabbbssssssggssrrrr"
String.split(str, "") |> Enum.chunk_while([], fn elem, acc ->
  cond do
    (length(acc) == 0) -> 
    {:cont, [elem]}
    (acc == [""]) -> 
      {:cont, [elem]}
    (List.last(acc) == elem) -> 
      {:cont, [elem | acc]}
    true -> 
    {:cont, Enum.reverse(acc), []}
  end
end,
fn
  [] -> {:cont, []}
  acc -> {:cont, Enum.reverse(acc), []}
end) |> Enum.map(fn e -> Enum.reduce(e, "", &<>/2) end) |> Enum.max_by(&String.length/1)

是否可以像 ruby 那样写一行或至少更短一些?

带块的链接 解决方案非常差。它执行几个绝对不需要的操作,如拆分、连接等,这可能会大大降低长输入的性能。

最简单的方法是使用带有 back reference.

的正则表达式
str = "aabbbssssssggssrrrr"
Regex.scan(~r/(.){1,}/, str, capture: :first)
#⇒ [["aa"], ["bbb"], ["ssssss"], ["gg"], ["ss"], ["rrrr"]]

现在如何获得最长的字符串是一个偏好问题,例如:

~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> Enum.sort_by(&-String.length(hd(&1)))
|> hd()
|> hd()
#⇒ "ssssss"

或者,List.flatten/1

~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> List.flatten()
|> Enum.sort_by(&-String.length(&1))
|> hd()
#⇒ "ssssss"

灵丹妙药的解决方案是使用Enum.reduce/3,这样O(N)只需要一次输入。

"aabbbssssssggssrrrr"
|> to_charlist()
|> Enum.reduce(%{char: ??, curr: 0, max: []}, fn
  ch, %{char: ch, max: max, curr: curr} when curr < length(max) -> 
    %{char: ch, max: max, curr: curr + 1}

  ch, %{char: ch, curr: curr} -> 
    %{char: ch, max: List.duplicate([ch], curr + 1), curr: curr + 1}

  ch, %{max: max} ->
    %{char: ch, max: max, curr: 1}
end)
|> Map.get(:max)
|> Enum.join()
#⇒ "ssssss"