Skip to content

Instantly share code, notes, and snippets.

@yuikns
Last active August 29, 2015 14:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yuikns/9b686fd07344855d3beb to your computer and use it in GitHub Desktop.
Save yuikns/9b686fd07344855d3beb to your computer and use it in GitHub Desktop.
import scala.collection.mutable.{ Map => MMap }
object Solution {
case class PrefixTrieNode(next: MMap[Char, PrefixTrieNode]) {
var v: Boolean = false
}
class PrefixTrieTree {
val root: PrefixTrieNode = PrefixTrieNode(MMap[Char, PrefixTrieNode]())
val insertMonitor = new AnyRef
def put(k: String) = {
var p = root
k.toCharArray.foreach { v =>
insertMonitor.synchronized {
p = p.next.getOrElseUpdate(v, PrefixTrieNode(MMap[Char, PrefixTrieNode]()))
}
}
p.v = true
}
def next(c: Char, n: PrefixTrieNode): Option[PrefixTrieNode] = n.next.get(c)
def next(c: Char): Option[PrefixTrieNode] = root.next.get(c)
def count(s: String) = {
val len = s.length
(0 to (len - 1)).par.foldLeft(0) { (l, c) =>
{
next(s(c)) match {
case Some(v) =>
var cnt = if (v.v) 1 else 0
var off = c + 1
var p = Option[PrefixTrieNode](v)
def get = {
if (off < len) {
p = next(s(off), p.get)
off += 1
p match {
case Some(add) =>
if (add.v)
cnt += 1
true
case None =>
false
}
} else {
false
}
}
while (get) {
//if (p.get.v) cnt += 1
}
cnt
case None =>
0
}
} + l
}
}
}
def main(args: Array[String]) {
val bi1 = scala.math.BigInt.long2bigInt(1)
val r = new PrefixTrieTree()
//r.put("1");
(0 to 801).par.foldLeft(bi1) { (l, c) =>
r.put(l.toString)
l * 2
}
(1 to Console.in.readLine().toInt).map { i =>
(Console.in.readLine(), i)
}.par.map { e =>
(e._2, r.count(e._1))
}.toArray.sortWith(_._1 < _._1).map(_._2).foreach { v =>
println(v)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment