三种方法：

1. 对每一个字符，从左右两边开始算

2. 动态规划

string input;

int length = input.length();

int[][] r= new int[length][length];

for (int i = length - 1; i >= 0; i --) {

　　for (int j = i; j < length; j++) {

　　　　if (i == j) {

　　　　　　r[i][j] = 1;

　　　　} else if ( input.charAt(i) == input.charAt(j)) {

　　　　　　if (i + 1 == j) {

　　　　　　　　r[i][j] = 2;

　　　　　　} else if (r[i+1][j - 1] != 0) {

　　　　　　　　r[i][j] = r[i + 1][ j - 1] + 2;

　　　　　　}  else {

　　　　　　　　r[i][j] = 0;

　　　　　　}

　　　　} else {

　　　　　　　　r[i][j] = 0;

　　　　}

　　}

}

3. Manacher's Algorithmn

https://www.hackerrank.com/topics/manachers-algorithm

http://algs4.cs.princeton.edu/53substring/Manacher.java.html