1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id$
package scala.collection.generic
/** KMP implementation, based on the undoubtedly reliable wikipedia entry.
*
* @author paulp
*/
object KMP {
private def KMP[B](S: Seq[B], W: Seq[B]): Option[Int] = {
// trivial cases
if (W.isEmpty) return Some(0)
else if (W drop 1 isEmpty) return (S indexOf W(0)) match {
case -1 => None
case x => Some(x)
}
val T: Array[Int] = {
val arr = new Array[Int](W.length)
var pos = 2
var cnd = 0
arr(0) = -1
arr(1) = 0
while (pos < W.length) {
if (W(pos - 1) == W(cnd)) {
arr(pos) = cnd + 1
pos += 1
cnd += 1
}
else if (cnd > 0) {
cnd = arr(cnd)
}
else {
arr(pos) = 0
pos += 1
}
}
arr
}
var m, i = 0
def mi = m + i
while (mi < S.length) {
if (W(i) == S(mi)) {
i += 1
if (i == W.length)
return Some(m)
}
else {
m = mi - T(i)
if (i > 0)
i = T(i)
}
}
None
}
def indexOf[B](
source: Seq[B], sourceOffset: Int, sourceCount: Int,
target: Seq[B], targetOffset: Int, targetCount: Int,
fromIndex: Int): Int =
KMP(source.slice(sourceOffset, sourceCount) drop fromIndex, target.slice(targetOffset, targetCount)) match {
case None => -1
case Some(x) => x + fromIndex
}
def lastIndexOf[B](
source: Seq[B], sourceOffset: Int, sourceCount: Int,
target: Seq[B], targetOffset: Int, targetCount: Int,
fromIndex: Int): Int = {
val src = (source.slice(sourceOffset, sourceCount) take fromIndex).reverse
val tgt = target.slice(targetOffset, targetCount).reverse
KMP(src, tgt) match {
case None => -1
case Some(x) => (src.length - tgt.length - x) + sourceOffset
}
}
}
|
