結果

問題 No.2231 Surprising Flash!
ユーザー wolgnikwolgnik
提出日時 2023-02-24 23:13:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,180 bytes
コンパイル時間 1,256 ms
コンパイル使用メモリ 82,096 KB
実行使用メモリ 142,036 KB
最終ジャッジ日時 2024-09-13 08:11:59
合計ジャッジ時間 7,866 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,352 KB
testcase_01 AC 49 ms
56,576 KB
testcase_02 WA -
testcase_03 AC 174 ms
77,440 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 52 ms
61,952 KB
testcase_09 WA -
testcase_10 AC 49 ms
61,440 KB
testcase_11 AC 151 ms
142,036 KB
testcase_12 AC 144 ms
136,372 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 146 ms
141,864 KB
testcase_16 AC 137 ms
90,668 KB
testcase_17 AC 142 ms
105,820 KB
testcase_18 AC 132 ms
117,880 KB
testcase_19 AC 133 ms
117,984 KB
testcase_20 AC 144 ms
115,736 KB
testcase_21 AC 131 ms
117,808 KB
testcase_22 AC 143 ms
116,100 KB
testcase_23 AC 130 ms
118,116 KB
testcase_24 AC 135 ms
118,184 KB
testcase_25 AC 133 ms
117,804 KB
testcase_26 AC 134 ms
118,088 KB
testcase_27 AC 135 ms
118,276 KB
testcase_28 AC 132 ms
117,944 KB
testcase_29 AC 163 ms
131,116 KB
testcase_30 AC 161 ms
131,300 KB
testcase_31 AC 157 ms
131,456 KB
testcase_32 AC 155 ms
124,964 KB
testcase_33 AC 139 ms
124,068 KB
testcase_34 AC 135 ms
124,504 KB
testcase_35 AC 137 ms
124,184 KB
testcase_36 AC 135 ms
124,264 KB
testcase_37 AC 131 ms
124,364 KB
testcase_38 AC 134 ms
124,484 KB
testcase_39 AC 94 ms
82,916 KB
testcase_40 AC 73 ms
79,128 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