結果

問題 No.1192 半部分列
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:42:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,236 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 173,120 KB
最終ジャッジ日時 2025-03-31 17:43:37
合計ジャッジ時間 4,890 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import bisect

def main():
    s = input().strip()
    t = input().strip()

    # Preprocess S: store positions for each character
    s_pos = defaultdict(list)
    for idx, c in enumerate(s):
        s_pos[c].append(idx)
    
    n = len(t)
    # Preprocess T: build next_pos array
    # next_pos[i][c] is the next position of character 'c' starting from index i in T
    next_pos = [{} for _ in range(n + 2)]  # +2 to handle i = n and i = n+1

    # Initialize for position n (all characters have next_pos as n)
    next_pos[n] = {chr(ord('a') + i): n for i in range(26)}
    # Build next_pos from the end of T backwards
    for i in range(n - 1, -1, -1):
        current = next_pos[i + 1].copy()
        current_char = t[i]
        current[current_char] = i
        next_pos[i] = current
    
    result = []
    current_t_pos = -1  # Last matched position in T
    i = 0  # Current position in S
    len_s = len(s)
    found_any = False  # Flag to check if any candidate was considered

    while i < len_s:
        found = False
        for c in 'abcdefghijklmnopqrstuvwxyz':
            # Find the first occurrence of c in s[i:]
            pos_list = s_pos.get(c, [])
            if not pos_list:
                continue  # No occurrence of this character
            # Find the first index >= i using binary search
            idx = bisect.bisect_left(pos_list, i)
            if idx == len(pos_list):
                continue  # No occurrence in the remaining part
            j = pos_list[idx]
            # Calculate next position in T
            current_t_next = current_t_pos + 1
            if current_t_next < 0:
                current_t_next = 0  # Handle initial case where current_t_pos is -1
            if current_t_next > n:
                next_t = n
            else:
                next_t = next_pos[current_t_next].get(c, n)
            
            if next_t < n:
                # Check if there are characters left in S after j
                if j + 1 < len_s:
                    # Can choose this c, and continue to build the result
                    result.append(c)
                    current_t_pos = next_t
                    i = j + 1
                    found = True
                    found_any = True
                    break
                else:
                    # No remaining characters, but this c would make a subsequence of T
                    # So skip this c
                    continue
            else:
                # Choosing c will make the result not a subsequence of T
                result.append(c)
                print(''.join(result))
                return
        if not found:
            break  # No valid characters could be chosen; break the loop
    
    # After building the result, check if it's not a subsequence of T
    # Also handle cases where no characters were chosen but possible empty string case
    def is_subsequence(sub, t_str):
        it = iter(t_str)
        return all(char in it for char in sub)
    
    if not result:
        print(-1)
    else:
        if is_subsequence(result, t):
            print(-1)
        else:
            print(''.join(result))

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