AtCoderBegginersSelection "白昼夢"

プログラミング

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream dreamer erase eraser のいずれかを追加する。

これは難しかった。
与えられた文字列Sが、条件の文字列の組み合わせから作ることができるかを判定しなさいという問題。
最初は、文字列Sを先頭から、条件の文字列と突合していけばいけるやん！と思ったのだが、先頭から見ていくと重複するように作られてるんですね。どういうことかというと、例えば、Sに"dreamer"という文字列が含まれている場合、本当は”dreamer"で判定OKにならないといけないのに、候補文字列の”dream"でも判定に引っ掛かり、残った"er"でどの候補文字列とも一致しなくなって、判定NGが出てくるようになってるんですよ。うーむ。。。困ったな。
先頭から見ていくのがダメなら、後ろから見ていくか？と気づいたのは、1時間以上考えてからでした（汗）。後ろからだと、重複部分がないんです！
それで提出したコードがつぎ。

# -*- coding: utf-8 -*-
# 英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
# T の末尾に dream dreamer erase eraser のいずれかを追加する。
def daydream(s):
    # 組合せ文字列→1文字ずつ判定に使えるようにリストで保持する
    dream = list("dream")
    dreamer = list("dreamer")
    erase = list("erase")
    eraser = list("eraser")
    # 組合せ文字列リスト
    stringList = [dream, dreamer, erase, eraser]
    # S == Tの判定結果
    ret = "YES"

    # 被判定文字列の文字数を取得
    i = len(s)-1
    # ループ１：被判定文字列を後ろから1文字ずつ確認する
    while i >= 0:
    # ループカウンタを被判定文字列へのポインタとして扱うためfor 文は使えない
    # for i in range(len(s)-1, -1, -1):
        flg = False
        # ループ２：組合せ文字列リストに格納されている文字列を1つずつ取り出す
        for j in range(len(stringList)):
            l = 0                                   # 被判定文字列のポインタ操作用変数
            # ループ３：組合せ文字列の後ろの文字から突合
            for k in range(len(stringList[j]) - 1 ,-1, -1):
                if s[i - l] != stringList[j][k]:    # 一致していない文字が出てきたら次の文字列へ
                    break                           # ループ３
                if k == 0:                          # 文字列と最後まで一致していれば
                    flg = True
                    i = i -len(stringList[j])       # 被判定文字のポインタを突合文字列の文字数分だけ前に進める
                l = l + 1                           # 被判定文字列の次の文字を確認するため操作用変数を1つ前へ
            if flg:
                break                               # ループ２
        if not flg: # どの組合せ文字列の文字とも一致しない場合は、S==T にならないのでNOを返す
            ret = "NO"
            break                                   # ループ１
    
    return ret

s = list(input())
print(daydream(s))

後ろから1文字ずつ、Sと候補文字列を突合していって、どの文字とも一致しなければS==Tにはならないと判定できる。
これで実現しようとしたときに、すべての文字列をリストに入れて、1文字ずつカウンタ変数で処理していこうと考えてた。C言語で文字列を扱うときにポインタを使うみたいに。それで最初はfor文のカウンタ変数i をポインタ代わりに使おうとしたんですけど、どうもうまくいかない。それでよくよく調べてみると、Pythonのfor文で使うrange()関数というのは、range型のオブジェクト（リストみたいな感じのデータ型らしい）を返し、for文ではそのオブジェクトの要素を1つずつ順に取り出してループさせる仕様みたい*1
なので、forループの中でカウンタ変数をいじくって処理を飛ばしたりさせることはできない。ループ冒頭で次の要素を取得してカウンタ変数に代入させるため、ループ内で値を変えてもリセットされるから。
そういう使い方をしたければ、ループ外で変数を用意してWhileループにして、カウンタ処理を記述するしかなさそう。
処理自体は、文字列Sを後ろから1文字ずつ、候補文字列の後ろから突合していく。うしろから突合していって、候補文字列の文字数分前に進めることができたら、その候補文字列とは一致していたということなので、Sの突合開始位置を、一致していた文字数分だけ前に進める。最後まで一致していれば、i は自動的に-1になり、一番大きいwhileループを抜けることができる。というのは、リストの初めの要素は0番目の要素なので、例えば残り5文字を突合して、一致していた場合、4（突合開始位置となるリストの添え字）-5（一致していた文字数）＝-1なので。

*1: