AGC006 A - Prefix and Suffix
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import numpy as np from numpy import linalg as LA # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N = ii() S = iss() T = iss() for i in range(N+1): for j in range(N): string = S[:i] + T[j:] if string[:N] == S and string[-N:] == T: print(len(string)) exit() if __name__ == '__main__': main()
考え方
文字列の長さが最長でも100
なので、
愚直に全探索します。
文字列S
の先頭からi(1 <= i <= N)
番目までの文字と、
文字列T
の末尾からj(0 <= i <= N)
番目までの文字の文字を接続した文字列を作成します。
作成した文字列の先頭からN
文字目までがS
と一致かつ末尾からN
文字までがT
と一致した文字列の最小文字列を回答とします。