/
ACAutoMata.kt
109 lines (99 loc) · 2.88 KB
/
ACAutoMata.kt
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package com.daily.algothrim.trie
import java.util.*
/**
* AC自动机, 字符串多模式串匹配
*/
class ACAutoMata {
companion object {
@JvmStatic
fun main(args: Array<String>) {
ACAutoMata().apply {
insert("ca".toCharArray())
insert("bc".toCharArray())
insert("bcd".toCharArray())
insert("abcd".toCharArray())
buildFailurePointer()
match("kdjafbcfjsk".toCharArray())
}
}
}
private val root = ACNode('/')
class ACNode(val data: Char) {
val children = Array<ACNode?>(26) { null }
var fail: ACNode? = null
var isEndingChar: Boolean = false
var length = -1
}
/**
* 将模式串插入trie树中
*/
fun insert(text: CharArray) {
var p = root
text.forEach {
val index = it - 'a'
if (p.children[index] == null) {
p.children[index] = ACNode(it)
}
p = p.children[index]!!
}
p.isEndingChar = true
p.length = text.size
}
/**
* 构建AC自动机
* O(k * len) k trie树的节点数 len 模式串的平均长度
*/
private fun buildFailurePointer() {
val queue = LinkedList<ACNode>()
queue.add(root)
while (queue.isNotEmpty()) {
val p = queue.remove()
var i = 0
while (i < 26) {
val pc = p.children[i++] ?: continue
if (p == root) {
pc.fail = root
} else {
var q = p.fail
while (q != null) {
val qc = q.children[pc.data - 'a']
if (qc != null) {
pc.fail = qc
break
}
q = q.fail
}
if (q == null) {
pc.fail = root
}
}
queue.add(pc)
}
}
}
/**
* 匹配主串
* O(n * len) n 主串长度 len 匹配的模式串长度
*/
private fun match(text: CharArray): Boolean {
var p: ACNode? = root
text.forEachIndexed { i, c ->
val index = c - 'a'
while (p?.children?.get(index) == null && p != root) {
p = p?.fail
}
p = p?.children?.get(index)
if (p == null) p = root
var temp = p
while (temp != null) {
if (temp.isEndingChar) {
println("match success! start: ${i - temp.length + 1}, match size: ${temp.length}")
return true
}
temp = temp.fail
}
}
println("match failure!")
return false
}
}