QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168281#80. Gluing PicturesdaarinsuTL 18ms11112kbPython32.0kb2023-09-08 07:11:442023-09-08 07:11:45

Judging History

你现在查看的是最新测评结果

  • [2023-09-08 07:11:45]
  • 评测
  • 测评结果:TL
  • 用时:18ms
  • 内存:11112kb
  • [2023-09-08 07:11:44]
  • 提交

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')

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: