結果

問題 No.1192 半部分列
ユーザー gew1fw
提出日時 2025-06-12 15:52:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,328 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 180,308 KB
最終ジャッジ日時 2025-06-12 15:52:47
合計ジャッジ時間 8,277 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 15 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    S = sys.stdin.readline().strip()
    T = sys.stdin.readline().strip()

    # Preprocess T's characters
    t_chars = [False] * 26
    for c in T:
        t_chars[ord(c) - ord('a')] = True

    # Preprocess next_pos for T
    n = len(T)
    next_pos = [dict() for _ in range(n + 1)]  # next_pos[i] for each i from 0 to n
    last = [-1] * 26

    for i in range(n - 1, -1, -1):
        c = T[i]
        c_idx = ord(c) - ord('a')
        for j in range(26):
            if j == c_idx:
                last[j] = i
            else:
                last[j] = last[j]
        # Update next_pos[i]
        for j in range(26):
            if last[j] != -1:
                next_pos[i][j] = last[j]
            else:
                next_pos[i][j] = -1

    # Handle position n
    for j in range(26):
        next_pos[n][j] = -1

    # Step 2: Check if there's a character in S not present in T
    min_char = None
    for c in S:
        c_idx = ord(c) - ord('a')
        if not t_chars[c_idx]:
            if min_char is None or c < min_char:
                min_char = c
    if min_char is not None:
        print(min_char)
        return

    # Function to check if a string is a subsequence of T
    def is_sub(s):
        t_ptr = 0
        for c in s:
            c_idx = ord(c) - ord('a')
            if t_ptr >= len(T):
                return False
            pos = next_pos[t_ptr].get(c_idx, -1)
            if pos == -1:
                return False
            t_ptr = pos + 1
        return True

    # Step 3: Check if S is a subsequence of T. If not, return S.
    if not is_sub(S):
        print(S)
        return

    # Step 4: If |S| > |T|, generate the smallest subsequence of length |T| + 1
    if len(S) > len(T):
        k = len(T) + 1
        stack = []
        for i, c in enumerate(S):
            while stack and stack[-1] > c and (len(stack) + (len(S) - i - 1)) >= k:
                stack.pop()
            stack.append(c)
        y_candidate = ''.join(stack[:k])
        print(y_candidate)
        return

    # Step 5: Check all prefixes of S
    for i in range(1, len(S) + 1):
        prefix = S[:i]
        if not is_sub(prefix):
            print(prefix)
            return

    # If all prefixes are subsequences of T
    print(-1)

if __name__ == "__main__":
    main()
0