Pythonでスタンプ操作により目標文字列を作る手順（インデックス配列）を求めるプログラム

小文字だけで構成された目標の文字列（ターゲット文字列）を作りたいとします。最初の時点では、長さ n の「?」（はてなマーク）だけが並んだシーケンスを持っており、これとは別に小文字からなる「スタンプ」が与えられます。各ターンでは、このスタンプをシーケンス上に重ねて押すことができ、重なった部分の文字がスタンプの対応する文字で置き換わります。使用できるターン数は最大でも 10 × n 回です。

例として、初期シーケンスが "?????"、スタンプが "abc" の場合を考えてみましょう。最初のターンで作れる文字列は "abc??"、"?abc?"、"??abc" のいずれかです。スタンプ操作によってターゲット文字列が作れる場合は、各ターンでスタンプを押した位置（左端の文字のインデックス）を配列として返します。どうしても作れない場合は空の配列を返します。たとえばシーケンスが "ababc"、スタンプが "abc" のとき、答えは [0, 2] になります。"?????" → "abc??" → "ababc" という順に変形できるためです。

入力が s = "abcd"、t = "abcdbcd" の場合、出力は [3, 0] となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• s の長さが 1 の場合：

  • t のすべての文字が s[0] と一致していれば、0 から t の長さまでのインデックスのリストを返し、そうでなければ空のリストを返します。

• ans := 新しいリスト

• t が「?」だけで構成されていない間、以下を繰り返します。

  • tmp := t（変更前の状態を保存）

  • i を 0 から s のサイズまで繰り返します。

    • j を s のサイズから i+1 まで逆順に繰り返します。

      • search := i 個の「?」 + s[i:j] の部分文字列 + (s のサイズ − j) 個の「?」 を連結したパターンを作成します。

      • search が t 内に存在する限り、以下を繰り返します。

        • search が見つかった位置を ans の末尾に追加します。

        • t := search を s のサイズ分の「?」で一度だけ置き換えます。

      • t がすべて「?」になったらループを抜けます。

    • t がすべて「?」になったら内側のループも抜けます。

  • tmp と t が同じまま（変化なし）であればループを抜けます。

実装例

理解を深めるために、次の実装を見てみましょう。

def solve(s, t):
    if len(s) == 1:
        return [i for i in range(len(t))] if all(c == s[0] for c in t) else []

    ans = []
    while t != "?" * len(t):
        tmp = t
        for i in range(len(s)):
            for j in reversed(range(i+1, len(s)+1)):
                search = "?" * i + s[i:j] + "?" * (len(s)-j)
                while t.find(search) != -1:
                    ans.append(t.find(search))
                    t = t.replace(search, "?"*len(s), 1)
                if t == "?" * len(t): break
            if t == "?" * len(t): break
        if tmp == t: return []
    return ans[::-1]

s = "abcd"
t = "abcdbcd"
print(solve(s, t))

入力

"abcd", "abcdbcd"

出力

[3, 0]