Two Two

这是HackerRank上的题目,在algorithm-string的倒数第二题.因为是练习scala,所以理所当然用scala来实现

题目很好理解,假定有个数据集y,为2的x次幂,x是值域为[0,800]的整数集合. 给定一个字符串,求问这个字符串中能找到多少个开始-结束的字符串,包含在数据集中.

首先需要注意一下x的值域为[0,800],因此1(=2^0)别忘记了,不然数字会少一些.

基本思路就是预处理首先生成一个2^0-2^800的字符串集合,然后匹配就是.

字符串匹配,首先想到的大约是kmp吧,不过此处是不合适的,因为我们有801条待匹配的字符串,效果是很快就TLE了.多个字符串匹配,其实首先应该考虑的是字典树.一个前缀树存下所有内容,每次就是搜索下就可以.

构造case class PrefixTrieNode如下:

import scala.collection.mutable.{ Map => MMap }

case class PrefixTrieNode(next: MMap[Char, PrefixTrieNode]) {
    var v: Boolean = false
}

每一个node都包含下个节点的map和一个boolean的v,v是标记本节点是否为终止节点,若发现v为true,说明可以匹配上一个字符串了.

然后弄个class(我取名叫PrefixTrieTree),放上put方法,如下:

class PrefixTrieTree {
    val root: PrefixTrieNode = PrefixTrieNode(MMap[Char, PrefixTrieNode]())

    val insertMonitor = new AnyRef

    def put(k: String) = {
      var p = root
      for (c <- k) {
        insertMonitor.synchronized {
          if (!p.next.contains(c)) {
            p.next += (c -> PrefixTrieNode(MMap[Char, PrefixTrieNode]()))
          }
        }
        p = p.next.get(c).get
      }
      p.v = true
    }
}

因为状态切换,在PrefixTrieTree中加上next方法

def next(c: Char, n: PrefixTrieNode): Option[PrefixTrieNode] = n.next.get(c)
def next(c: Char): Option[PrefixTrieNode] = root.next.get(c)

最后,也是最重要的,我们构造一个trie tree后,怎样使用它.

最开始,我考虑的是维护一个array,首先查看root开始是否有以当前char为key的next node,有的话把它加入队列.然后检查队列,分别查看每个队列中的元素,是否有以当前char为key的下一个,若有则切换状态.这样一路下去.查看新的队列中的v是否为true,若是counter+1.最后我们就可以得到总得结果.

代码如下:

def count(s: String) = {
  s.toCharArray.foldLeft((0, Array[PrefixTrieNode]().par)) { (l, c) =>
    val n = l._2.flatMap { p =>
      next(c, p)
    }
    next(c) match {
      case Some(v) =>
        if (v.v) {
          (l._1 + n.count(_.v) + 1, n :+ v)
        } else {
          (l._1 + n.count(_.v), n :+ v)
        }
      case None =>
        (l._1 + n.count(_.v), n)
    }
  }._1
}

看起来很有道理的样子--但实际上还是TLE.原因是切换太多了,而且基本是串行的,并行效果很不好. 为了让程序能更好地并行,修改count如下:

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) {}
          cnt
        case None =>
          0
      }
    } + l
}

完整代码参考此处.

这样写就直接过了.

scala和c++其实还是有很多的区别的,我第一个count主要还是c++的思维,因为自己管理内存,在有可能的情况下,我会尽可能考虑不要老是push&pop环境,而是倾向于维持一个状态机,不断滚下去.但在scala中,并行可以很好地控制一些context,而我们主要需要做的是让程序减少互相之间的依赖,能够更好地并行.