-
Notifications
You must be signed in to change notification settings - Fork 31
/
ZAlgorithm-Online.go
129 lines (112 loc) · 2.51 KB
/
ZAlgorithm-Online.go
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 可以插入字符的在线z函数
// https://ei1333.github.io/library/string/z-algorithm.hpp
// 每个后缀s[i:]与s的最长公共前缀长度
// aaabaaaab
// 921034210
// ZAlgorithm(s) // s: string
// Append(c) // c: string
// Get(i) // i: index
// GetAll() // return []int
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
yosupo()
}
func demo() {
s := "aaabaaaab"
Z := NewZAlgoOnline(0, func(i int) int { return int(s[i]) })
fmt.Println(Z.GetAll())
Z.Append(97) // 97 is the ascii code of 'a'
fmt.Println(Z.GetAll())
Z.Append(97) // 97 is the ascii code of 'a'
fmt.Println(Z.GetAll())
fmt.Println(Z.ords)
}
func yosupo() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var s string
fmt.Fscan(in, &s)
n := len(s)
Z := NewZAlgoOnline(0, func(i int) int { return int(s[i]) })
for i := 0; i < n; i++ {
Z.Append(int(s[i]))
}
res := Z.GetAll()
for _, v := range res {
fmt.Fprint(out, v, " ")
}
}
type ZAlgoOnline struct {
ords []int
deleted []bool
deletedHist [][]int32
z []int32
cur []int32
}
func NewZAlgoOnline(n int, f func(i int) int) *ZAlgoOnline {
res := &ZAlgoOnline{}
for i := 0; i < n; i++ {
res.Append(f(i))
}
return res
}
func (za *ZAlgoOnline) Append(c int) {
za.ords = append(za.ords, c)
za.deletedHist = append(za.deletedHist, []int32{})
za.deleted = append(za.deleted, false)
za.z = append(za.z, 0)
za.z[0]++
len_ := int32(len(za.ords))
if len_ == 1 {
return
}
if za.ords[0] == c {
za.cur = append(za.cur, len_-1)
} else {
za.deleted[len_-1] = true
}
set := func(t, l int32) {
za.deleted[t] = true
for int32(len(za.deletedHist)) <= l {
za.deletedHist = append(za.deletedHist, []int32{})
}
za.deletedHist[l] = append(za.deletedHist[l], t)
za.z[t] = l - t - 1
}
for len(za.cur) > 0 {
t := za.cur[0]
if za.deleted[t] {
za.cur = za.cur[1:]
} else if za.ords[len_-t-1] == za.ords[len(za.ords)-1] {
break
} else {
set(t, len_)
za.cur = za.cur[1:]
}
}
if len(za.cur) > 0 {
t := za.cur[0]
for _, p := range za.deletedHist[len_-t] {
set(p+t, len_)
}
}
}
func (za *ZAlgoOnline) Get(i int) int {
if za.deleted[i] {
return int(za.z[i])
}
return len(za.ords) - i
}
func (za *ZAlgoOnline) GetAll() []int {
res := make([]int, len(za.ords))
for i := 0; i < len(za.ords); i++ {
res[i] = za.Get(i)
}
return res
}