import scala.
io.
StdIn.
readLine import scala.
collection.
mutable.
PriorityQueue import scala.
annotation.
tailrec import scala.
util.
control.
Breaks
// ex. b = 26 (if alphabet), mod = 1000000007
class RollingHash
[T
](val b
: Long,
val mod
: Long,
val conv
: T
=> Long
) { final def hash
(n
: T
) : Long
= conv
(n
)%mod
// n = (c0,c1,c2,c3,...cn)
// => (c0*b^n + ... + cn*b^0) mod 'mod'
n.foldLeft(0l)((c,t) => (conv(t)+b*c)%mod)
n.scanLeft(0l)((c,t) => (conv(t)+b*c)%mod)
final def apply
(n
: Traversable
[T
]) = hash
(n
) }
def apply
[T
](b
: Long, mod
: Long, conv
: T
=> Long
) = new RollingHash
(b,mod,conv
) }
}
}
// def insert(s : String, c : Char, n : Int) : String = {
// val (head,tail) = s.splitAt(n)
// head + c + tail
// }
// def solve(s : String) : Option[String] = {
// val n = s.length
// val b = new Breaks
// def check(s : String,c : Char) : Boolean = {
// val n = s.length
// (0 until s.length).forall((i) => {
// val j = n - i - 1
// s(i) == c || s(j) == c || s(i) == s(j)
// })
// }
// if(check(s,'?')){
// Some(s.take(n/2) + s(n/2) + s.drop(n/2))
// }else{
// var ans : Option[String] = None
// b.breakable {
// for(i <- 0 until n){
// val j = n - i - 1
// if(s(i) != s(j)){
// val checking = Vector((s.take(i) + "?" + s.drop(i)),
// (s.take(j+1) + "?" + s.drop(j+1)))
// checking.foreach((i) => if(check(i,'?')){
// val r = i.indexOf('?')
// ans = Some(i.updated(r,i(n-r)))
// })
// b.break
// }
// }
// }
// ans
// }
// }
// rsexr
def solve
(s
: String
) : Option
[String
] = { val r
= Lib.
String.
RollingHash(103,
1000000007,
(c
: Char
) => c-
'a'+
1) val a
= r.
scan(s
).
toVector val b
= r.
scan(s.
reverse).
toVector val p
= (0 to n
).
scanLeft(1l
)((i,j
) => (i
*r.
b % r.
mod)) def insert
(hashlist
: Vector
[Long
], c
: Char, i
: Int
) : Long
= { val left
= (hashlist
(i
) * p
(n-i
)) % r.
mod val right
= (hashlist
(n
) - left + r.
mod) % r.
mod val ins
= (r
(c
) * p
(n-i
)) % r.
mod val here
= (r.
b * left + ins + right
) % r.
mod here
}
var ret
: Option
[String
] = None
bk.breakable {
c <- 'a' to 'z'){
if(insert
(a,c,i
) == insert
(b,c,n-i
)){ ret = Some(s.take(i) + c + s.drop(i))
bk.break
}
}
}
ret
// (for(i <- 0 to n;
// c <- 'a' to 'z') yield (i,c))
// .filter({case (i,c) => insert(a,c,i) == insert(b,c,n-i)})
// .headOption
// .map({case (i,c) => s.take(i) + c + s.drop(i)})
}
def main
(args
: Array
[String
]) : Unit
= { }
println(ret)
}
}
aW1wb3J0IHNjYWxhLmlvLlN0ZEluLnJlYWRMaW5lCmltcG9ydCBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUHJpb3JpdHlRdWV1ZQppbXBvcnQgc2NhbGEuYW5ub3RhdGlvbi50YWlscmVjCmltcG9ydCBzY2FsYS51dGlsLmNvbnRyb2wuQnJlYWtzCgpvYmplY3QgTGliIHsKICBvYmplY3QgU3RyaW5nIHsKICAgIC8vIGV4LiBiID0gMjYgKGlmIGFscGhhYmV0KSwgbW9kID0gMTAwMDAwMDAwNwogICAgY2xhc3MgUm9sbGluZ0hhc2hbVF0odmFsIGIgOiBMb25nLHZhbCBtb2QgOiBMb25nLHZhbCBjb252IDogVCA9PiBMb25nKSB7CiAgICAgIGZpbmFsIGRlZiBoYXNoKG4gOiBUKSA6IExvbmcgPSBjb252KG4pJW1vZAogICAgICAvLyBuID0gKGMwLGMxLGMyLGMzLC4uLmNuKQogICAgICAvLyAgPT4gKGMwKmJebiArIC4uLiArIGNuKmJeMCkgbW9kICdtb2QnCiAgICAgIGZpbmFsIGRlZiBoYXNoKG4gOiBUcmF2ZXJzYWJsZVtUXSkgPQogICAgICAgIG4uZm9sZExlZnQoMGwpKChjLHQpID0+IChjb252KHQpK2IqYyklbW9kKQogICAgICBmaW5hbCBkZWYgc2NhbihuIDogVHJhdmVyc2FibGVbVF0pID0KICAgICAgICBuLnNjYW5MZWZ0KDBsKSgoYyx0KSA9PiAoY29udih0KStiKmMpJW1vZCkKICAgICAgZmluYWwgZGVmIGFwcGx5KG4gOiBUKSA9IGhhc2gobikKICAgICAgZmluYWwgZGVmIGFwcGx5KG4gOiBUcmF2ZXJzYWJsZVtUXSkgPSBoYXNoKG4pCiAgICB9CiAgICBvYmplY3QgUm9sbGluZ0hhc2ggewogICAgICBkZWYgYXBwbHlbVF0oYiA6IExvbmcsIG1vZCA6IExvbmcsIGNvbnYgOiBUID0+IExvbmcpID0gbmV3IFJvbGxpbmdIYXNoKGIsbW9kLGNvbnYpCiAgICB9CiAgfQp9CgpvYmplY3QgTWFpbiB7CiAgLy8gZGVmIGluc2VydChzIDogU3RyaW5nLCBjIDogQ2hhciwgbiA6IEludCkgOiBTdHJpbmcgPSB7CiAgLy8gICB2YWwgKGhlYWQsdGFpbCkgPSBzLnNwbGl0QXQobikKICAvLyAgIGhlYWQgKyBjICsgdGFpbAogIC8vIH0KICAvLyBkZWYgc29sdmUocyA6IFN0cmluZykgOiBPcHRpb25bU3RyaW5nXSA9IHsKICAvLyAgIHZhbCBuID0gcy5sZW5ndGgKICAvLyAgIHZhbCBiID0gbmV3IEJyZWFrcwogIC8vICAgZGVmIGNoZWNrKHMgOiBTdHJpbmcsYyA6IENoYXIpIDogQm9vbGVhbiA9IHsKICAvLyAgICAgdmFsIG4gPSBzLmxlbmd0aAogIC8vICAgICAoMCB1bnRpbCBzLmxlbmd0aCkuZm9yYWxsKChpKSA9PiB7CiAgLy8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2YWwgaiA9IG4gLSBpIC0gMQogIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcyhpKSA9PSBjIHx8IHMoaikgPT0gYyB8fCBzKGkpID09IHMoaikKICAvLyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9KQogIC8vICAgfQogIC8vICAgaWYoY2hlY2socywnPycpKXsKICAvLyAgICAgU29tZShzLnRha2Uobi8yKSArIHMobi8yKSArIHMuZHJvcChuLzIpKQogIC8vICAgfWVsc2V7CiAgLy8gICAgIHZhciBhbnMgOiBPcHRpb25bU3RyaW5nXSA9IE5vbmUKICAvLyAgICAgYi5icmVha2FibGUgewogIC8vICAgICAgIGZvcihpIDwtIDAgdW50aWwgbil7CiAgLy8gICAgICAgICB2YWwgaiA9IG4gLSBpIC0gMQogIC8vICAgICAgICAgaWYocyhpKSAhPSBzKGopKXsKICAvLyAgICAgICAgICAgdmFsIGNoZWNraW5nID0gVmVjdG9yKChzLnRha2UoaSkgKyAiPyIgKyBzLmRyb3AoaSkpLAogIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKHMudGFrZShqKzEpICsgIj8iICsgcy5kcm9wKGorMSkpKQogIC8vICAgICAgICAgICBjaGVja2luZy5mb3JlYWNoKChpKSA9PiBpZihjaGVjayhpLCc/JykpewogIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdmFsIHIgPSBpLmluZGV4T2YoJz8nKQogIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYW5zID0gU29tZShpLnVwZGF0ZWQocixpKG4tcikpKQogIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0pCiAgLy8gICAgICAgICAgIGIuYnJlYWsKICAvLyAgICAgICAgIH0KICAvLyAgICAgICB9CiAgLy8gICAgIH0KICAvLyAgICAgYW5zCiAgLy8gICB9CiAgLy8gfQogIC8vIHJzZXhyCiAgZGVmIHNvbHZlKHMgOiBTdHJpbmcpIDogT3B0aW9uW1N0cmluZ10gPSB7CiAgICB2YWwgciA9IExpYi5TdHJpbmcuUm9sbGluZ0hhc2goMTAzLDEwMDAwMDAwMDcsKGMgOiBDaGFyKSA9PiBjLSdhJysxKQogICAgdmFsIGEgPSByLnNjYW4ocykudG9WZWN0b3IKICAgIHZhbCBiID0gci5zY2FuKHMucmV2ZXJzZSkudG9WZWN0b3IKICAgIHZhbCBuID0gcy5sZW5ndGgKICAgIHZhbCBwID0gKDAgdG8gbikuc2NhbkxlZnQoMWwpKChpLGopID0+IChpKnIuYiAlIHIubW9kKSkKICAgIGRlZiBpbnNlcnQoaGFzaGxpc3QgOiBWZWN0b3JbTG9uZ10sIGMgOiBDaGFyLCBpIDogSW50KSA6IExvbmcgPSB7CiAgICAgIHZhbCBsZWZ0ICA9IChoYXNobGlzdChpKSAqIHAobi1pKSkgICAgICUgci5tb2QKICAgICAgdmFsIHJpZ2h0ID0gKGhhc2hsaXN0KG4pIC0gbGVmdCArIHIubW9kKSAlIHIubW9kCiAgICAgIHZhbCBpbnMgICA9IChyKGMpICogcChuLWkpKSAgICAgICAgICAgICAgJSByLm1vZAogICAgICB2YWwgaGVyZSA9IChyLmIgKiBsZWZ0ICsgaW5zICsgcmlnaHQpICUgci5tb2QKICAgICAgaGVyZQogICAgfQoKICAgIHZhciByZXQgOiBPcHRpb25bU3RyaW5nXSA9IE5vbmUKICAgIHZhbCBiayA9IG5ldyBCcmVha3MKICAgIGJrLmJyZWFrYWJsZSB7CiAgICAgIGZvcihpIDwtIDAgdG8gbjsKICAgICAgICAgIGMgPC0gJ2EnIHRvICd6Jyl7CiAgICAgICAgaWYoaW5zZXJ0KGEsYyxpKSA9PSBpbnNlcnQoYixjLG4taSkpewogICAgICAgICAgcmV0ID0gU29tZShzLnRha2UoaSkgKyBjICsgcy5kcm9wKGkpKQogICAgICAgICAgYmsuYnJlYWsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHJldAogICAgIC8vIChmb3IoaSA8LSAwIHRvIG47CiAgICAgLy8gICAgIGMgPC0gJ2EnIHRvICd6JykgeWllbGQgKGksYykpCiAgICAgLy8gIC5maWx0ZXIoe2Nhc2UgKGksYykgPT4gaW5zZXJ0KGEsYyxpKSA9PSBpbnNlcnQoYixjLG4taSl9KQogICAgIC8vICAuaGVhZE9wdGlvbgogICAgIC8vICAubWFwKHtjYXNlIChpLGMpID0+IHMudGFrZShpKSArIGMgKyBzLmRyb3AoaSl9KQogIH0KCiAgZGVmIG1haW4oYXJncyA6IEFycmF5W1N0cmluZ10pIDogVW5pdCA9IHsKICAgIHZhbCBzID0gcmVhZExpbmUKICAgIHZhbCByZXQgPSBzb2x2ZShzKSBtYXRjaCB7CiAgICAgICAgY2FzZSBTb21lKGopID0+IGoKICAgICAgICBjYXNlIE5vbmUgICAgPT4gIk5BIgogICAgICB9CiAgICBwcmludGxuKHJldCkKICB9Cn0=