最尤推定 2 Python3編（paizaランク S 相当）

図のような状態遷移図があり、次の条件を満たす文字列 X があります。
条件: 文字列 X は初期状態と最終状態を 0 (図における赤い頂点) とする経路のラベルから生成される



Paiza 君はこの状態遷移図から生成された文字列 X をもとにした文字列 S を受け取りました。
文字列 S は文字列 X に対して次のような誤りが 0 個以上含まれています｡
誤り: 文字列中の文字が 「0 から 1」 または 「1 から 0」 に変わる。
ただし、文字列の同じ位置に対して誤りは高々 1 回しか起きない。

今、正しい文字列 X を知りたいですが、文字列 S 以外の手がかりはありません。
そこで、Paiza 君は状態遷移図から条件を満たして生成される同じ長さの文字列の中で、「文字列 S との誤りの個数が最小のもの」を X とみなすことにしました。
あなたは Paiza 君の代わりに文字列 X を 推定します。
まず、誤りの個数として考えられる最小値を出力してください。
次に、誤りの個数が最小であると考えられる文字列 (すなわち X として推測したもの) を辞書順で全て出力してください。
ただし、入力では文字列 X を推測した候補が 100 個以下に絞れるような文字列 S のみが与えられます。

必要に応じて以下に示す状態遷移図のラベル付き隣接リストを利用しても構いません。

// 状態遷移図のラベル付き隣接リスト(C++用)
// AL[u]:= 頂点 u から出る辺の(行き先となる頂点v, 辺のラベル)のペアの配列
const vector<vector<pair<int, string>>> AL = {
    {{0, "00"}, {2, "01"}},
    {{0, "10"}, {2, "11"}},
    {{1, "01"}, {3, "00"}},
    {{1, "11"}, {3, "10"}}};

# 状態遷移図のラベル付き隣接リスト(Python3用)
 # AL[u]:= 頂点 u から出る辺の(行き先となる頂点v, 辺のラベル)のタプルのリスト
AL = [
    [(0, "00"), (2, "01")],
    [(0, "10"), (2, "11")],
    [(1, "01"), (3, "00")],
    [(1, "11"), (3, "10")]]

例えば、入力例 1 では S として 110111 が与えられます。
このとき、状態遷移図から生成される文字列で条件を満たすのは
000000 (経路: 0→0→0→0) と 010110 (経路: 0→2→1→0) の 2 つです。
000000が X であると仮定すると、誤りの個数は 5 個となります。
010110が X であると仮定すると、誤りの個数は 2 個となります。
したがって、X を 010110 とみなし、誤りの個数の最小値は 2 となります。

入力例 2 では S として 0101111110 が与えられます。
このとき、X を 0101110110 (経路: 0→2→1→2→1→0) とみなすと、誤りの個数は 1 となり、これが最小の値です。

入力例 3 では S として 01000100 が与えられます。
このとき、X を 00000000 (経路: 0→0→0→0→0) か 01001110 (経路: 0→2→3→1→0) とみなすと、誤りの個数は 2 となり、これが最小の値です。
このように X の候補を 1 つに絞れないこともあります。