这一题是USACO所有题目中我最自豪的一个题目，首先因为大部分人的代码都是在小数后一位上，而我这个算法是O(n)的，所以非常的快。又因为这是我自己想出来的，而且思维角度比较独特，所以我甚为自豪！
但是我这个思路很难表达清晰。
想把它单独提出来作为一篇文章(http://zqynux.blog.163.com/blog/static/1674995972010929683892/)写，包裹题解也在左边的链接里面，写好了把链接贴上来。
这里我犯的几个错误分别如下：
LANG: C
ID: yylogoo2
PROG: calfflac
/
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#define EQ(a, b) (toupper(a) == toupper(b))
char str[20001];
/ 记录以i结尾的回文数的另外一头的坐标:start[i] /
int start[20001];
/ 记录纯净长度, 把空格和标点符号去掉的长度 /
int num[20001];
/ 寻找一个字母, way 为1时向后寻找, way为-1时向前寻找 /
int find(int s, int way)
{
int t = s;
while(t >= 0 && !isalpha(str[t])){
t += way;
}
return t;
}
int main(void)
{
int i, t, j;
int len = 0;
int max = 1;
int end = 0;
freopen("calfflac.in", "r", stdin);
freopen("calfflac.out", "w", stdout);
while(fgets(&str[len], 20000 – len, stdin) != NULL){
len += strlen(&str[len]);
}
for(i = 1; i < len; i++){
if(!isalpha(str[i])){
num[i] = num[i – 1];
start[i] = start[i – 1];
/
Mistack 3:
忘记添加continue了，进入这个的时候num[i]就会改变，
下一次DP时会有错误。
/
continue;
}
/
Mistack 2:
下面应该是使用start[i – 1]的前一个字符进行比较
/
t = find(start[i – 1] – 1, –1);
/
Mistack 1:
在比较字母是否相等时，忽略了大小写。
/
if(t >= 0 && EQ(str[t], str[i])){
num[i] = num[i – 1] + 2;
start[i] = t;
}else{
/ t = find(i – 1, -1);
j = find(i + 1, 1);
if(str[t] == str[j]){
num[i] = 3;
start[i] = t;
}else if(str[t] == str[i]){
num[i] = 2;
start[i] = t;
}/
t = find(i – 1, –1);
if(t > 0 && EQ(str[i], str[t])){
num[i] = 2;
start[i] = t;
}else{
num[i] = 1;
start[i] = i;
}
}
if(num[i] > max){
max = num[i];
end = i;
}
}
printf("%d\n", max);
for(i = start[end]; i <= end; i++){
printf("%c", str[i]);
}
printf("\n");
return 0;
}