-
Notifications
You must be signed in to change notification settings - Fork 513
/
c.go
50 lines (46 loc) · 907 Bytes
/
c.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
package main
import (
"bufio"
. "fmt"
"io"
"os"
)
/*
用 KMP 可以求出既是 s 前缀也是 s 后缀的子串长度 match
统计出 match[1..n-1] 中的最大值 mxM
若 t 在 s 中间存在,则 match[n-1], match[match[n-1]-1], ... 中必然存在一个不超过 mxM 的数
*/
// github.com/EndlessCheng/codeforces-go
func run(_r io.Reader, out io.Writer) {
in := bufio.NewReader(_r)
var T int
var s string
o:
for Fscan(in, &T); T > 0; T-- {
Fscan(in, &s)
n := len(s)
match := make([]int, n)
mxM := 0
for i, c := 1, 0; i < n; i++ {
b := s[i]
for c > 0 && s[c] != b {
c = match[c-1]
}
if s[c] == b {
c++
}
match[i] = c
if i < n-1 && c > mxM {
mxM = c
}
}
for c := match[n-1]; c > 0; c = match[c-1] {
if c <= mxM {
Fprintln(out, s[:c])
continue o
}
}
Fprintln(out, "not exist")
}
}
func main() { run(os.Stdin, os.Stdout) }