# 2009a 文字列照合

def search2(T, P):
    # 配列CとDの初期化（P.length分のサイズを確保）
    # 空白 " " や初期値として -1 を入れておきます
    C = [" "] * len(P)
    D = [-1] * len(P)

    # (1): 表の作成
    # 疑似言語の for j を 1 から P.length-1 まで は、Pythonでは 0 から len(P)-2 に対応
    for j_idx in range(len(P) - 1):
        j = j_idx + 1  # 疑似言語の1始まりのjを再現
        
        # 疑似言語の for k を 1 から j まで
        for k_idx in range(j):
            k = k_idx + 1  # 疑似言語の1始まりのkを再現
            
            # C[k]とP[j]が等しい、またはC[k]が空白文字と等しい場合
            # ※Pythonのインデックスは 0始まりなので [k-1], [j-1] としています
            if C[k - 1] == P[j - 1] or C[k - 1] == " ":
                C[k - 1] = P[j - 1]
                D[k - 1] = len(P) - j  # [ウ] に入る P.length - j
                break

    # 文字列を照合する
    i = 1  # [ウ] の初期化処理（1始まりとして管理）
    
    # i が [ア] (T.length - P.length + 1) 以下である間繰り返す
    while i <= (len(T) - len(P) + 1):
        
        # (2): 文字の比較
        match_success = True
        # j を 1 から [イ] (P.length) まで
        for j_idx in range(len(P)):
            j = j_idx + 1
            
            # T[i+j-1] と P[j] の比較
            if T[(i + j - 1) - 1] == P[j - 1]:
                # j と [イ] (P.length) が等しい（＝最後まで一致した）
                if j == len(P):
                    return i  # 発見した位置 i (1始まり) を返す
            else:
                match_success = False
                break  # 不一致なら内側ループを抜ける
                
        # (3): スキップ数の決定
        d = len(P)  # デフォルトのスキップ数（その他の文字用、基本はP.length）
        
        # k を 1 から P.length まで
        for k_idx in range(len(P)):
            k = k_idx + 1
            
            # 判定文字 T[i+P.length-1] と表の比較
            判定文字 = T[(i + len(P) - 1) - 1]
            if C[k - 1] == 判定文字 or C[k - 1] == " ":
                d = D[k - 1]
                break
                
        # 表に該当がなかった（その他の文字）場合の安全弁
        if d == -1 or d == " ":
            d = len(P)
            
        i = i + d  # 位置をスキップ数分進める

    return -1  # 見つからなかった場合

# --- 動作検証 ---
# 設問3のデータでテスト
text = "PICKLED PEPPER"
pattern = "PEP"

result = search2(text, pattern)
print(f"最初に一致した位置 (1始まり): {result}") 
# 出力結果: 9 （問題の通り、9文字目の 'P'EPPER から一致します）