Paperfolding文字列¶
初期文字 \(a\) , \(b\) , \(c\) , \(d\) による \(n\) 番目のPaperfolding文字列
・P(n) = dummy
・P(n) = dummy
注 ：\(n\) を大きい数にするとおかしくなります．(入力制限で \(n<30\) としています)
アルゴリズムはループの方を使用．
定義¶
\(n\) 番目の Paperfolding文字列 (Paperfolding Word) \(P_n\) を以下のような定義で生成する．
また，\(P_{n}\) は， \(P_{n-1}\) に対して次の規則に従った変換を行うことにより生成することもできる． ただし， \(P_0 = a\) とする．
- \(a → ab\)
- \(b → cb\)
- \(c → ad\)
- \(d → cd\)
性質¶
- \(a → 0\)
- \(b → 0\)
- \(c → 1\)
- \(d → 1\)
の置き換えを行うと
- \(z_{4n}=0\)
- \(z_{4n+2}=1\)
- \(z_{2n+1}=z_n\)
が成立する文字列になる．
Paperfolding wordに含まれる回文の長さは{0,1,2,3,4,5,6,7,9,11,13}となり14文字以上の長さの回文は出現しない.
( \(n =\) 5のとき初めて13文字の回文が出現する.)