fork(13) download 
  1. import scala.collection.immutable.TreeSet
  2.  
  3. object Main extends App {
  4.   implicit class Word(val repr: String)
  5.   implicit def unword(w: Word) = w.repr
  6.   implicit val wordOrdering = Ordering.fromLessThan[Word](_ != _)
  7.  
  8.   def solve(items: Set[Word], anagrams: String) = {
  9.     def branch(trial: String, position: Int, candidates: Set[Word]): Option[Seq[(String, String)]] = {
  10.       val label = anagrams.substring(position, position + trial.length)
  11.       if (trial.sorted == label.sorted) {
  12.         if (candidates.isEmpty) Option(Seq((trial, label)))
  13.         else candidates.view
  14.           .map(newTrial => branch(newTrial, position + trial.length, candidates - newTrial))
  15.           .find(_.isDefined).flatten.map((trial, label) +: _)
  16.       } else None
  17.     }
  18.     items.view.map(item => branch(item, 0, items - item)).find(_.isDefined).flatten
  19.   }
  20.  
  21.   val items = TreeSet(readLine().split(" ").map(new Word(_)) : _*)
  22.   val anagrams = readLine()
  23.  
  24.   solve(items, anagrams) match {
  25.     case None => println("Ne fart")
  26.     case Some(solution) =>
  27.       val (items, labels) = solution.unzip
  28.       labels.foreach(s => print(s + " "))
  29.       println()
  30.       items.foreach(s => print(s + " "))
  31.   }
  32. }
Success #stdin #stdout 0.44s 382272KB
comments (?)
stdin 
abab ab ab ab ab ab ab ab ab ab ab ab
abababababababababababaabb
stdout 
ab ab ab ab ab ab ab ab ab ab ab aabb 
ab ab ab ab ab ab ab ab ab ab ab abab
https://ideone.com/7IKaKq
language:
Scala (scala 2.12.8)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!