Palindome

Definition

A palindome is a string which reads the same backward or forward

Example: abbabababba

Note

Palindromes in \(abbabababba\). ※Palindomes of length 0 and 1 are ommited.

i	1	2	3	4	5	6	7	8	9	10	11
character	a	b	b	a	b	a	b	a	b	b	a
Length 2		b	b
Length 2									b	b
Length 3			b	a	b
Length 3				a	b	a
Length 3					b	a	b
Length 3						a	b	a
Length 3							b	a	b
Length 4	a	b	b	a
Length 4								a	b	b	a
Length 5			b	a	b	a	b
Length 5				a	b	a	b	a
Length 5					b	a	b	a	b
Length 7			b	a	b	a	b	a	b
Length 9		b	b	a	b	a	b	a	b	b
Length 11	a	b	b	a	b	a	b	a	b	b	a

Definition of palindrome in Wikipedia (http://en.wikipedia.org/wiki/Palindrome).

“A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward, such as madam or kayak.”

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

Algorithms

Given a string, output all palindrome in the string.

Naive algorithm

• Find palindrome for each length of substring.

Output all palindromes

text =

Reference

Gusfield, Dan. "Algorithms on strings, trees, and sequences." ACM SIGACT News 28.4 (1997): 197-198.