結果

問題 No.2231 Surprising Flash!
コンテスト
ユーザー wolgnik
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 32 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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