求最长的回文字符串

程序：输入：一行字符串，输出：最长的回文字符的长度以及把它们给输出来。 　　

如： 　　输入：1596156432111234 　　　　

输出：6 　　　　432111234

　　回文的性质

首先先把题目撇开，单说回文数的性质，如abcba是一个长度为5的回文数，那它有什么性质呢？ 　　回文数顾名思义，就是从左念和从右念是相同的，也可以说从左遍历和从右遍历是相同的，这些都是废话。因为它是回文数所以可以同时从左和右开始遍历，各 个字符都是相同的。 　　

其实上面那些性质也没什么用，算是铺垫吧，接下来的才是重点，那怎么样去构成一个回文数呢？就用abcba做例子吧，这个回文数的构成是由单个字符c两边同时放置b，构成的bcb再两边同时放置一个a构成的。

　　回文的判定

那么假设要你判断abcba是不是有两种方法，但是我要说的不是两边同时开始遍历并且判断的方法，再用abcbad做例子吧，用程序判断它是不是一个回文数，我先把过程写出来，然后再把方式写出来。 下面把回文数和回文混用。 　　

首先下标i=0...5，s[i]代表第i个字符。

i从1开始递归，因为第一个字符不存在回文数， i=1时，当前回文长度为1，就是单个字符b。

当前回文数长度 是我自己定义的名词，就是说以i结尾的回文数的长度。

然后i = 2时，当前回文数是单个字符c，长度为1；

i=3时，这里需要注意一下了，从这里开始就有一些变化了，当前回文数的长度为3，为bcb，

i=4时，当前回文数的长度为5，为abcba，

i=5，当前回文长度为1，是单个字符d，这样它就不是一个回文数。

　　当前回文数长度

那么求当前回文数的长度(不是标准的语言)： 　　

        i = 1 　　

        while(i 123321吧，

当i = 3时(1233 21 )，

start[i] = 2(1 23 321) len[i] = 2；

当i = 5时(123321 )，

start[i] = 0(1 23321)，len[i] = 6，

也就是说当前回文数的取决于三种情况： 　　

第一种：start[i - 1]的前面一个字符等于i时，当前回文就是(start[i - 1] - 1) ~ i，长度就是len[i - 1] + 2。 　　

第二种：s[i - 1]等于s[i]，就是说两个相邻的字符相等的话，那么start[i] = i - 1；len[i] = 2。 　　

第三种：什么都不是，就是单个字符回文,start[i] = i, len[i] = 1。 　　

其实仔细想想可以把len[]这个数组去掉，因为len[i] = i - start[i] + 1;  　　

但是 ，因为这篇文章时根据USACO那题写的，那个题目的s[](字符串)中包含空格和标点符号，但是又把它们记入len[]中，所以这个代码只是一个模式，遇到不同的题目要有不同的待遇，但是这种思想我觉得很重要/神奇，类似于DP但又不是。

　　解题

那么上面的题目就好解了（只给出大致代码）： 　　

i = 1, ans = 0 　　

while(i < n)

{ 　　　　

if(s[start[i - 1] - 1] == s[i])

{ 　　　　　　

start[i] = start[i - 1] - 1; 　　　　　　

len[i] = len[i - 1] + 2; 　　　　

}

else if(s[i - 1] == s[i])

{ 　　　　　　

start[i] = i - 1; 　　　　　　

len[i] = 2; 　　　　

}

else

{ 　　　　　　

start[i] = i; 　　　　　　

len[i] = 1; 　　　　

} 　　　　

if(ans < len[i])

{ 　　　　　　

ans = len[i]; 　　　　　　

k = i; 　　　　

} 　　

} 　　

printf("%d\n", ans); 　　

for(i = start[k]; i <= k; i++)

{ 　　　　

printf("%c", s[i]); 　　

}