結果

問題 No.1909 Detect from Substrings
ユーザー lam6er
提出日時 2025-03-31 17:49:29
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,464 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 848,260 KB
最終ジャッジ日時 2025-03-31 17:50:29
合計ジャッジ時間 6,411 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = input[idx].strip()
        S.append(s)
        idx += 1
    
    if N == 0:
        print(0)
        return
    
    # Generate all possible candidates from the first string
    first = S[0]
    candidates = set()
    for pos in range(M + 1):
        for c in 'abcdefghijklmnopqrstuvwxyz':
            new_str = first[:pos] + c + first[pos:]
            candidates.add(new_str)
    
    # Check each candidate against all S_i
    valid_count = 0
    candidate_list = list(candidates)  # To potentially iterate faster
    
    for candidate in candidate_list:
        all_valid = True
        for s in S:
            i = 0  # pointer for candidate (T)
            j = 0  # pointer for current S_i
            len_c = len(candidate)
            len_s = len(s)
            # Early check for lengths (though given, may not be necessary)
            if len_s != M or len_c != M + 1:
                all_valid = False
                break
            while i < len_c and j < len_s:
                if candidate[i] == s[j]:
                    j += 1
                i += 1
            if j != len_s:
                all_valid = False
                break
        if all_valid:
            valid_count += 1
    
    print(valid_count)

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