.. -*- coding: utf-8; -*-

=================
回文 (palindrome)
=================

回文の定義
~~~~~~~~~~

左から読んでも右から読んでも同じものを **回文**  *(palindrome)* と呼ぶ

例)
abbabababba

.. note::
	:math:`abbabababba` に含まれる回文.	※0文字（:math:`\varepsilon`）,1文字は省略してあります.
   
   ======= == == == == == == == == == == ==
   i       1  2  3  4  5  6  7  8  9  10 11
   ======= == == == == == == == == == == ==
   文字   　a  b  b  a  b  a  b  a  b  b  a
   ------- -- -- -- -- -- -- -- -- -- -- --
   長さ2       b  b                           
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ2                           b  b    
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ3         b  a  b           
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ3            a  b  a                
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ3               b  a  b           
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ3                  a  b  a          
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ3                     b  a  b           
   ------- -- -- -- -- -- -- -- -- -- -- --	
   長さ4   a  b  b  a                      
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ4                        a  b  b  a 
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ5         b  a  b  a  b       
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ5            a  b  a  b  a         
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ5               b  a  b  a  b       
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ7         b  a  b  a  b  a  b                              
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ9      b  b  a  b  a  b  a  b  b                            
   ------- -- -- -- -- -- -- -- -- -- -- --	   
   長さ11  a  b  b  a  b  a  b  a  b  b  a                           
   ======= == == == == == == == == == == ==



Wikipedia(http://ja.wikipedia.org/wiki/%E5%9B%9E%E6%96%87)の定義では

「回文（かいぶん）とは、始めから（通常通り）読んだ場合と終わりから（通常と逆に）読んだ場合とで文字や音節の出現する順番が変わらず、なおかつ、言語としてある程度意味が通る文字列のことで、言葉遊びの一種である。」

.. 
	todo::

	例）面白い回文


なお、仙台市内にある *作並温泉* は **回文の里** として有名である（http://kaibun.sakunami-spa.com/）




アルゴリズム
======================
入力として与えられた文字列の中に含まれるすべての回文を列挙する問題

素朴な手法
 - 部分文字列の長さごとに文字列の頭から回文かどうか判定し，回文なら出力.
	
.. literalinclude:: /Scripts/Python/palindrome.py
   :pyobject: pal


.. 
	todo::
	- 線形時間のもの（誰かお願い）

 * Richard Groult, Élise Prieur, and Gwénaël Richommec, "Counting distinct palindromes in a word in linear time" Information Processing Letters, Volume 110, Issue 20, pp.908-912, 30 September 2010 <http://www.sciencedirect.com/science/article/pii/S002001901000236X> 
   文字列 :math:`w` に含まれる相異なる回文の数を :math:`O(|w|)` で求める
 
含まれるpalindromeを出力
==========================================

.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/palindrome.js">
         </script>

          <form onsubmit="return false;" autocomplete="off">
          <div>
          text = <input id="text" type="text" size="64" value="aba"/>
		  </div>
		  </form>
		  <div id="pal" ></div>
		  
参考文献
--------
.. * XXXXX
.. raw:: html

	Gusfield, Dan. "Algorithms on strings, trees, and sequences." ACM SIGACT News 28.4 (1997): 197-198.
	<!-- <a href="http://www.academia.edu/download/31053376/Algorithms_on_String_Trees_and_Sequences.pdf" target="_blank">link(PDF)</a> -->