結果

問題 No.1909 Detect from Substrings
ユーザー lam6er
提出日時 2025-04-15 23:47:05
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,231 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 81,904 KB
実行使用メモリ 848,688 KB
最終ジャッジ日時 2025-04-15 23:49:40
合計ジャッジ時間 5,101 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    S = []
    for _ in range(N):
        S.append(input[idx])
        idx += 1

    # Generate all possible T from S[0]
    s0 = S[0]
    possible_T = set()
    for pos in range(M + 1):
        for c in 'abcdefghijklmnopqrstuvwxyz':
            T = s0[:pos] + c + s0[pos:]
            possible_T.add(T)

    # Check each candidate T against all other S_i
    count = 0
    for T in possible_T:
        valid = True
        for s in S[1:]:
            # Check if s is a subsequence of T
            it = iter(T)
            for ch in s:
                found = False
                while True:
                    try:
                        t_ch = next(it)
                        if t_ch == ch:
                            found = True
                            break
                    except StopIteration:
                        break
                if not found:
                    valid = False
                    break
            if not valid:
                break
        if valid:
            count += 1

    print(count)

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