結果

問題 No.2231 Surprising Flash!
ユーザー wolgnikwolgnik
提出日時 2023-02-24 23:13:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,180 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 87,240 KB
実行使用メモリ 141,676 KB
最終ジャッジ日時 2023-10-11 08:58:04
合計ジャッジ時間 9,602 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
71,400 KB
testcase_01 AC 85 ms
71,336 KB
testcase_02 WA -
testcase_03 AC 207 ms
79,364 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 86 ms
75,864 KB
testcase_09 WA -
testcase_10 AC 83 ms
76,468 KB
testcase_11 AC 182 ms
141,676 KB
testcase_12 AC 168 ms
135,948 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 174 ms
141,608 KB
testcase_16 AC 163 ms
92,296 KB
testcase_17 AC 173 ms
103,164 KB
testcase_18 AC 158 ms
117,984 KB
testcase_19 AC 158 ms
117,976 KB
testcase_20 AC 170 ms
117,008 KB
testcase_21 AC 155 ms
117,996 KB
testcase_22 AC 171 ms
116,672 KB
testcase_23 AC 157 ms
118,244 KB
testcase_24 AC 162 ms
117,980 KB
testcase_25 AC 159 ms
117,988 KB
testcase_26 AC 160 ms
117,960 KB
testcase_27 AC 157 ms
118,068 KB
testcase_28 AC 160 ms
117,980 KB
testcase_29 AC 189 ms
126,376 KB
testcase_30 AC 181 ms
126,216 KB
testcase_31 AC 181 ms
126,276 KB
testcase_32 AC 184 ms
126,464 KB
testcase_33 AC 165 ms
124,172 KB
testcase_34 AC 162 ms
124,120 KB
testcase_35 AC 160 ms
124,152 KB
testcase_36 AC 166 ms
124,264 KB
testcase_37 AC 162 ms
123,888 KB
testcase_38 AC 159 ms
124,132 KB
testcase_39 AC 131 ms
87,008 KB
testcase_40 AC 111 ms
83,592 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p] or text[i] == "?":
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res
  def period(self, i): return i + 1 - self.table[i + 1]

for _ in range(int(input())):
  N, M = map(int, input().split())
  S = list(input())[: -1][: : -1]
  T = list(input())[: -1][: : -1]

  kmp = KmpSearch(T).search(S)

  if len(kmp) == 0:
    print(-1)
    continue

  res = S[: : -1]
  r = N - kmp[0]
  l = r - M
  res[l: r] = T[: : -1]
  for i in range(N):
    if res[i] == "?": res[i] = "a"
  print("".join(res))
0