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 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
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,而我们主要需要做的是让程序减少互相之间的依赖,能够更好地并行.