結果
問題 |
No.2231 Surprising Flash!
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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))