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

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



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

今、正しい文字列 X を知りたいですが、文字列 S 以外の手がかりはありません。
そこで、Paiza 君は状態遷移図から条件を満たして生成される同じ長さの文字列の中で、「文字列 S との誤りの個数が最小のもの」を X とみなすことにしました。
あなたは Paiza 君の代わりに文字列 X を 推定します。
この問題では誤りの個数として考えられる最小値を出力してください。

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

// 状態遷移図のラベル付き隣接リスト(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 が与えられます。
このとき、状態遷移図から生成される、条件を満たす長さ |S|=6 の文字列は
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 つに絞れないこともあります。