QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168281 | #80. Gluing Pictures | daarinsu | TL | 18ms | 11112kb | Python3 | 2.0kb | 2023-09-08 07:11:44 | 2023-09-08 07:11:45 |
Judging History
answer
from sys import stdin, stdout
MAX_SIZE = 200_000
ALPHABET_SIZE = 26
class Node:
def __init__(self):
self.next = [0] * ALPHABET_SIZE
self.link = 0
self.len = 0
nodes = [0] * (MAX_SIZE * 2)
size = last = 0
city = ''
def init_tree():
global last, size
nodes[last] = Node()
nodes[last].link = -1
nodes[last].len = 0
size += 1
last = 0
def expand_tree(char):
global last, size
current = size
size += 1
nodes[current] = Node()
nodes[current].len = nodes[last].len + 1
parent = last
while parent != -1 and nodes[parent].next[char] == 0:
nodes[parent].next[char] = current
parent = nodes[parent].link
if(parent == -1):
nodes[current].link = 0
else:
q = nodes[parent].next[char]
if(nodes[parent].len + 1 == nodes[q].len):
nodes[current].link = q
else:
clone = size
size += 1
nodes[clone] = Node()
nodes[clone].len = nodes[parent].len + 1
nodes[clone].next = nodes[q].next
nodes[clone].link = nodes[q].link
while parent != -1 and nodes[parent].next[char] == q:
nodes[parent].next[char] = clone
parent = nodes[parent].link
nodes[q].link = nodes[current].link = clone
last = current
ord_a = 65 # ord('A')
def build_tree():
global city
init_tree()
for char in city:
char_int = ord(char) - ord_a
expand_tree(char_int)
city = stdin.readline().strip('\n')
build_tree()
for i in range(int(stdin.readline())):
name = stdin.readline().strip('\n')
current_pos = 0
total = 0
for char in name:
char_int = ord(char) - ord_a
char_pos = nodes[current_pos].next[char_int]
if(char_pos):
current_pos = char_pos
continue
if(char_pos == 0):
current_pos = 0
total += 1
char_pos = nodes[0].next[char_int]
if(char_pos == 0):
stdout.write('-1\n')
break
current_pos = char_pos
else:
total += 1
total = str(total)
stdout.write(total+'\n')
詳細信息
Test #1:
score: 100
Accepted
time: 18ms
memory: 11112kb
input:
MONTEVIDEO 4 DEMONIO MONTE EDIT WON
output:
4 1 4 -1
result:
ok 4 lines
Test #2:
score: -100
Time Limit Exceeded
input:
PMZTZCUOYRAGXNGRENYXYCCPULCJLITRFEDMDJPMOUDGQPLOWXFHWNVWMVJGVNZLRGLRDWISNZHZOZOIYNYHEWNLJFELOLASYVUDEMGHVLGQHGQNCGQLIAAEGIDCSXFTIUOYXMORUBLKOXQROPWRTAFXXOJNREOZMUCEAQESMHBTQAEPITRPCFQKSWAOMHTIHJRBKHJYOBJTKOPGYIZVJJFCGIKZDLSVGCQDTKGRXYECUOQGCISMBLKGHXXWLFCGQWLMPUKZCWLUMSOOIHFEKUJSPTBUCNFTFDNNUNDTKDCK...