結果

問題 No.1909 Detect from Substrings
ユーザー lam6er
提出日時 2025-03-20 20:38:10
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,876 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 594,204 KB
最終ジャッジ日時 2025-03-20 20:38:30
合計ジャッジ時間 6,564 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 MLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    idx = 0
    N, M = int(input[idx]), int(input[idx+1])
    idx += 2
    input_set = set()
    input_list = []
    for _ in range(N):
        s = input[idx]
        idx += 1
        input_set.add(s)
        input_list.append(s)
    
    valid_t = set()
    seen_candidates = set()
    
    for s in input_list:
        s_len = len(s)
        # Generate all possible T_candidate by inserting a character into s
        for pos in range(s_len + 1):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                # Create candidate T
                t_candidate = s[:pos] + c + s[pos:]
                if t_candidate in seen_candidates:
                    continue
                seen_candidates.add(t_candidate)
                
                # Check if all input strings are deletions of t_candidate
                all_valid = True
                for check_s in input_list:
                    if len(check_s) != M:
                        all_valid = False
                        break
                    if not is_deletion(check_s, t_candidate):
                        all_valid = False
                        break
                if all_valid:
                    valid_t.add(t_candidate)
    
    print(len(valid_t))

def is_deletion(s, t):
    if len(s) != len(t) - 1:
        return False
    i = j = 0
    skipped = False
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            if not skipped:
                skipped = True
                j += 1
            else:
                return False
    # Check remaining characters in t if needed
    if not skipped:
        j += 1
    # Ensure all of s is matched and exactly one character skipped
    return i == len(s) and j == len(t)

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