結果

問題 No.1909 Detect from Substrings
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:54:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,505 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 848,096 KB
最終ジャッジ日時 2025-06-12 14:57:05
合計ジャッジ時間 7,412 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def is_subsequence(s, t):
    it = iter(t)
    return all(c in it for c in s)

def generate_candidates(s):
    candidates = set()
    for i in range(len(s)+1):
        for c in 'abcdefghijklmnopqrstuvwxyz':
            new_s = s[:i] + c + s[i:]
            candidates.add(new_s)
    return candidates

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

    if N ==0:
        print(0)
        return

    # Generate candidates from S[0]
    candidates = generate_candidates(S[0])

    # Now, for each candidate, check against all other S
    count =0
    for t in candidates:
        valid = True
        for s in S[1:]:
            if len(t) != len(s)+1:
                valid = False
                break
            # Check if t can be formed by inserting exactly one character into s
            # So, t must be a supersequence of s with exactly one extra character
            # Check if s is a subsequence of t
            if not is_subsequence(s, t):
                valid = False
                break
            # Additionally, t must be formed by inserting exactly one character into s, which is already ensured
            # by t being a candidate generated from inserting one character into S[0], and being a supersequence
        if valid:
            count +=1
    print(count)

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