fork download
copy 
  1. import scala.io.StdIn.readLine
  2. import scala.collection.mutable.PriorityQueue
  3. import scala.annotation.tailrec
  4. import scala.util.control.Breaks
  5.  
  6. object Lib {
  7.   object String {
  8.     // ex. b = 26 (if alphabet), mod = 1000000007
  9.     class RollingHash[T](val b : Long,val mod : Long,val conv : T => Long) {
  10.       final def hash(n : T) : Long = conv(n)%mod
  11.       // n = (c0,c1,c2,c3,...cn)
  12.       //  => (c0*b^n + ... + cn*b^0) mod 'mod'
  13.       final def hash(n : Traversable[T]) =
  14.         n.foldLeft(0l)((c,t) => (conv(t)+b*c)%mod)
  15.       final def scan(n : Traversable[T]) =
  16.         n.scanLeft(0l)((c,t) => (conv(t)+b*c)%mod)
  17.       final def apply(n : T) = hash(n)
  18.       final def apply(n : Traversable[T]) = hash(n)
  19.     }
  20.     object RollingHash {
  21.       def apply[T](b : Long, mod : Long, conv : T => Long) = new RollingHash(b,mod,conv)
  22.     }
  23.   }
  24. }
  25.  
  26. object Main {
  27.   // def insert(s : String, c : Char, n : Int) : String = {
  28.   //   val (head,tail) = s.splitAt(n)
  29.   //   head + c + tail
  30.   // }
  31.   // def solve(s : String) : Option[String] = {
  32.   //   val n = s.length
  33.   //   val b = new Breaks
  34.   //   def check(s : String,c : Char) : Boolean = {
  35.   //     val n = s.length
  36.   //     (0 until s.length).forall((i) => {
  37.   //                                 val j = n - i - 1
  38.   //                                 s(i) == c || s(j) == c || s(i) == s(j)
  39.   //                               })
  40.   //   }
  41.   //   if(check(s,'?')){
  42.   //     Some(s.take(n/2) + s(n/2) + s.drop(n/2))
  43.   //   }else{
  44.   //     var ans : Option[String] = None
  45.   //     b.breakable {
  46.   //       for(i <- 0 until n){
  47.   //         val j = n - i - 1
  48.   //         if(s(i) != s(j)){
  49.   //           val checking = Vector((s.take(i) + "?" + s.drop(i)),
  50.   //                                 (s.take(j+1) + "?" + s.drop(j+1)))
  51.   //           checking.foreach((i) => if(check(i,'?')){
  52.   //                              val r = i.indexOf('?')
  53.   //                              ans = Some(i.updated(r,i(n-r)))
  54.   //                            })
  55.   //           b.break
  56.   //         }
  57.   //       }
  58.   //     }
  59.   //     ans
  60.   //   }
  61.   // }
  62.   // rsexr
  63.   def solve(s : String) : Option[String] = {
  64.     val r = Lib.String.RollingHash(103,1000000007,(c : Char) => c-'a'+1)
  65.     val a = r.scan(s).toVector
  66.     val b = r.scan(s.reverse).toVector
  67.     val n = s.length
  68.     val p = (0 to n).scanLeft(1l)((i,j) => (i*r.b % r.mod))
  69.     def insert(hashlist : Vector[Long], c : Char, i : Int) : Long = {
  70.       val left  = (hashlist(i) * p(n-i))     % r.mod
  71.       val right = (hashlist(n) - left + r.mod) % r.mod
  72.       val ins   = (r(c) * p(n-i))              % r.mod
  73.       val here = (r.b * left + ins + right) % r.mod
  74.       here
  75.     }
  76.  
  77.     var ret : Option[String] = None
  78.     val bk = new Breaks
  79.     bk.breakable {
  80.       for(i <- 0 to n;
  81.           c <- 'a' to 'z'){
  82.         if(insert(a,c,i) == insert(b,c,n-i)){
  83.           ret = Some(s.take(i) + c + s.drop(i))
  84.           bk.break
  85.         }
  86.       }
  87.     }
  88.     ret
  89.      // (for(i <- 0 to n;
  90.      //     c <- 'a' to 'z') yield (i,c))
  91.      //  .filter({case (i,c) => insert(a,c,i) == insert(b,c,n-i)})
  92.      //  .headOption
  93.      //  .map({case (i,c) => s.take(i) + c + s.drop(i)})
  94.   }
  95.  
  96.   def main(args : Array[String]) : Unit = {
  97.     val s = readLine
  98.     val ret = solve(s) match {
  99.         case Some(j) => j
  100.         case None    => "NA"
  101.       }
  102.     println(ret)
  103.   }
  104. }
Success #stdin #stdout 0.43s 322112KB
comments (?)
stdin
copy 
aac
stdout
copy 
caac
https://ideone.com/FbsCXm
language:
Scala (scala 2.12.8)
created:
8 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!