結果

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

ソースコード

diff #
raw source code 

def is_one_char_deletion(T, S):
    len_T = len(T)
    len_S = len(S)
    if len_T != len_S + 1:
        return False
    i = j = 0
    allowed_skips = 1
    while i < len_S and j < len_T:
        if S[i] == T[j]:
            i += 1
            j += 1
        else:
            if allowed_skips:
                allowed_skips -= 1
                j += 1
            else:
                return False
    # Handle remaining characters
    if allowed_skips:
        # Check if the remaining characters in T are one more than S
        return i == len_S and j == len_T - 1
    return i == len_S and j == len_T

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    S_list = []
    for _ in range(N):
        S = input[idx]
        idx += 1
        S_list.append(S)
    
    if N == 0:
        print(0)
        return
    
    first_S = S_list[0]
    possible_T = set()
    # Generate all possible T by inserting one character into first_S
    for pos in range(M+1):
        for c in 'abcdefghijklmnopqrstuvwxyz':
            new_T = first_S[:pos] + c + first_S[pos:]
            possible_T.add(new_T)
    
    count = 0
    for T in possible_T:
        valid = True
        for S in S_list:
            if not is_one_char_deletion(T, S):
                valid = False
                break
        if valid:
            count += 1
    print(count)

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