为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/calfflac
[编辑] 分析
没什么好说的，硬搜，数据刚好不会超时。
枚举中间数（也就是认为它是回文数最中间的字母），然后左右扩展（忽略非字母）至出界和不相等。最后更新最大值。
要考虑回文是奇数和偶数两种情况。提示大家在开始扩展之前就判断（很巧妙，大家举几个例子就可以明白了）
输入中的换行符可以维持原样不变，PASCAL和C不会输出成乱码。
Usaco的数据有点弱了，提供一个样例：axazzaxazza，卡传统的DP。
想到了爆搜，从头开始枚举每一个点，然后再从这个点向后搜，找到每一个和它相同的点，判断是否是回文
结果此算法超时.... (107229HR写:通过优化,这一题搞定了,但时间不少 Executing...
Test 1: TEST OK [0.000 secs, 3068 KB] Test 2: TEST OK [0.000 secs, 3068 KB] Test 3: TEST OK [0.000 secs, 3068 KB] Test 4: TEST OK [0.000 secs, 3068 KB] Test 5: TEST OK [0.000 secs, 3068 KB] Test 6: TEST OK [0.054 secs, 3068 KB] Test 7: TEST OK [0.027 secs, 3068 KB] Test 8: TEST OK [0.594 secs, 3068 KB]
) 给大家一个警示... ——pollow
Executing...
Test 1: TEST OK [0.000 secs, 324 KB] Test 2: TEST OK [0.000 secs, 324 KB] Test 3: TEST OK [0.000 secs, 324 KB] Test 4: TEST OK [0.000 secs, 324 KB] Test 5: TEST OK [0.000 secs, 324 KB] Test 6: TEST OK [0.011 secs, 324 KB] Test 7: TEST OK [0.000 secs, 324 KB] Test 8: TEST OK [0.205 secs, 324 KB]
枚举回文字串的中间值，左右拓展。对于这种弱弱的题目没有必要后缀数组啊dp啊什么的，此算法正确性高，空间复杂度完全可以接受，就是慢了点而已。（也就test 8慢了点，其他甚至比更优的算法要好
Executing...
Test 1: TEST OK [0.000 secs, 412 KB] Test 2: TEST OK [0.000 secs, 412 KB] Test 3: TEST OK [0.000 secs, 412 KB] Test 4: TEST OK [0.000 secs, 412 KB] Test 5: TEST OK [0.000 secs, 412 KB] Test 6: TEST OK [0.000 secs, 412 KB] Test 7: TEST OK [0.000 secs, 412 KB] Test 8: TEST OK [0.081 secs, 412 KB]
直接枚举中间点吧。。。很快的 只要分奇偶两种情况讨论就行了
下面和下面的下面的DP的方法是错误的 修正的DP方法在下面的下面的下面
来说说一种O(n)的动态规划算法。 方程f[i]=f[i-1]+2 如果(a[i]=a[i-f[i-1]-1])
或 f[i]=2 如果(a[i]=a[i-1])
或 f[i]=1
其中f[i]是以恰好第i个字符结尾的回文串最大长
速度巨快如雷电...
USER: Vegetable frogl1
TASK: calfflac
LANG: PASCAL
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 320 KB] Test 2: TEST OK [0.000 secs, 324 KB] Test 3: TEST OK [0.000 secs, 320 KB] Test 4: TEST OK [0.000 secs, 320 KB] Test 5: TEST OK [0.011 secs, 324 KB] Test 6: TEST OK [0.000 secs, 324 KB] Test 7: TEST OK [0.011 secs, 324 KB] Test 8: TEST OK [0.000 secs, 324 KB]
All tests OK.
貌似是错误的方法 反例:aaa
如果序列是cbbabbab 那么倒数第二个字母的a，按照程序的话应该f[7]=1,但实际上是4
应该按回文串长度的奇偶性分别进行动规
如楼上所言，楼上的楼上所说方法错误，axazzaxazza和aaa都得出错误答案，但usaco上能过。 稍作改进就完全对了，应该分奇偶讨论，dp两次： 奇数:
初始化：dp1[1]=1; dp1[i]=dp1[i-dp1[i-1]-1]+2；（若a[i]=a[i-dp1[i-1]-1]） 否则 dp1[i]=1;
偶数：
初始化：dp2[1]=0; dp2[i]=dp2[i-dp2[i-1]-1]+2；（若a[i]=a[i-dp2[i-1]-1]） 否则 dp2[i]=0;
两次dp需要各开一个数组：dp1[]，dp2[] 取两次dp中的最大值，并判断该值是属于奇数偶数， 判断有点费劲，我是这么做的：
int tg=1,i,ans=1;
for(i=1;i<=n;i++) ans=dp1[ans]<dp1[i]?i:ans;
for(i=1;i<=n;i++) if(dp1[ans]<dp2[i]){ans=i;tg=2;break;}
for(i++;i<=n;i++) if(dp2[ans]<dp2[i]) ans=i;
if(tg==1) 是奇数，按dp1[]数组输出
else 是偶数，按dp2[]数组输出
修正：楼上几楼的都不对吧， 对于楼楼楼上，如果是cbbabbab的话，如楼上所说错误，不多赘述 对于楼楼上所举的楼楼楼上的反例，表示完全正确 对于楼上，如果是abbaabba，那么dp2[]是0 0 2 4 0 0 2 4，而正确的是0 0 2 4 2 4 6 8 而事实证明，楼上的算法基本正确，但如果再加上楼楼楼上的一条语句在dp2[]的赋值里就可以了 正解应为： 奇数:
初始化：dp1[1]=1; dp1[i]=dp1[i-dp1[i-1]-1]+2；（若a[i]=a[i-dp1[i-1]-1]） 否则 dp1[i]=1;
偶数：
初始化：dp2[1]=0; dp2[i]=dp2[i-dp2[i-1]-1]+2；（若a[i]=a[i-dp2[i-1]-1]） dp2[i]=2 （若a[i]=a[i-1]） 否则 dp2[i]=0;
by SkipperHXY
我有一个超快的思路~! DP.. 用:
f[i].max表示以i结尾的回文数最大的长度为多少.. f[i].start 表示以i结尾的回文数的开头在哪里..
则：
f[i] = f[i - 1] + 2 (如果以i结尾回文数的两头i - 1的两头加一的话.) f[i] = 3 (如果以i - 1为回文数的中心的话) f[i] = 2 (如果是偶数会问的话) f[i] = 1 (否则)
USER: Qingyang Zhang [zqynux11] TASK: calfflac LANG: C
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 1956 KB] Test 2: TEST OK [0.000 secs, 1956 KB] Test 3: TEST OK [0.000 secs, 1956 KB] Test 4: TEST OK [0.000 secs, 1956 KB] Test 5: TEST OK [0.000 secs, 1956 KB] Test 6: TEST OK [0.000 secs, 1956 KB] Test 7: TEST OK [0.000 secs, 1956 KB] Test 8: TEST OK [0.000 secs, 1956 KB]
为了方便阐述，插在了楼上和楼下中间，则楼下所说的“上述”就是我的楼上所述。 如楼下所讲，楼上的方法从本质上是错误的，即漏过了长回文串中的子回文串。但是，这并不影响我们求出正确答案。 借用楼下的例子扩展：cabbaabba(a)bbaa 先看最早的一个回文串abbaabba，那么下一个字符,被括号括起来的a,用楼上的算法应该是f[10]=2（与前面一个a形成回文串a(a)），但实际上这个a可以与前面的字符串形成回文串aabba(a)，即f[10]=6。 这样看起来这个算法是错误的，但是这并不影响我们求出正确答案。我们来看这个做法的正确性： 算法忽略掉了长回文串中的子回文串，但是子回文串长度<=根回文串，就是说忽略这个子回文串没有关系。我们继续看，以这个(a)为中心，继续DP，可以得到串aabba(a)bbaa，长度为10，比原来的那个大。这从另一个方面说明，用DP来找回文串，关键在于定位中心。
其实有很多的DP算法是漏掉一部分状态的（好像有一个VIJOS的邮局题），不过这样没关系，只要能求出正解，时空复杂度低就是好的算法。 /*by zqynux11*/
这里再插一段话吧！（如果我对各位的叙述没有理解到位还请指出来）
同样为了方便叙述插在楼上和楼下的中间，还请见谅。
考虑这么一个序列：q[(xyxdxyx)dxyx]c.（括号是为了叙述方便，字符串不含括号）。如果用第一次提到的那个动规，
f[7]=7(就是小括号末尾的那个x，以它结尾的最长回文串长是7)，没有问题。继续算f[8]=1,f[9]=3,f[10]=5,f[11]=7,f[12]=1. 可是实际上，最长回文子串是中括号括起来的部分，长为11.所以这个动规方法还是错误的。尽管某个回文串的回文子串长度不会超过它 本身，却完全有可能再加上若干个字符以后变成更长的回文串。
我表示同意楼下的观点，必须考虑到以某个字符结尾的所有回文串的长度。那个O(N)的方法只是凑巧算对了答案而已，测试数据太弱了。
结束！
<by TapTop>
//by kuramaw1
上述DP算法,从本质上讲是错误的,并不是回文长度的奇偶性的问题,f[i]表示是恰好以第i个字符结尾的回文串最大长度,
当计算f[i]时,它只不比较a[i]与a[i-f[i-1]-1]是否相等,如果相等,则扩展回文串,即f[i]=f[i-1]+2,当比较不相等时,此时应该考考虑扩展恰好以i-1个字符结符结尾的次最长的回文串,直至以i-1个字符结尾的回文串长度为0,而上述DP算法只考虑扩展恰好以第i个字符结尾的最长的回文串和最短的回文串(即0,此时比较的是a[i],与a[i-f[i-1]-1],也就是a[i]与a[i-1]).上述DP算法,只要f[i]的回文串中出现恰好以i个字符结束的子回文就会发生错误.
例如:
cabbaabbaa,f[9]=8,此时的回文件串abbaabba,计算f[10]时,'a'!='c',然后就直接比较a[10]与a[9],得到f[10]=2,其实f[9],abbaabba存在一个回文子串abba,此时应该比较a[10]与a[9-4-1]='a',即可得到正确答案f[10]=6,相当于是扩展了abba.,
正解的话,必需求出以i结尾所有长度的回文子串,复杂度应是o(n*n)
下面有一个简单的算法实现流程
令b[i][j]表示是否存在恰好以i个字符尾长度为j的回文串(其中 0<=j<=i)
f[i]表示是恰好以第i个字符结尾的回文串最大长度
//令b初始化为flase;
b[1][0]=true; b[1][1]=true; f[1]=1 for(int i=2;i<len;i++) { f[i]=-1; b[i][0]=true; for(j=i-1;j>=0;j--) if(b[i-1][j]) { if(i-j-1>0 && a[i]==a[i-j-1]) { b[i][j+2]=true; if (j+2>f[i]) f[i]=j+2; } } }
一个整体O(n)的算法（参考许智磊论文）
整体用后缀数组实现。
求以i为中心向两边扩展的最远值，等价于求Suffix(i)和Suffix(i')的最长公共前缀。 其中i'=2n-i+2
解法： 1.初始化答案为0。S=T+'#'+Reverse(T)+$，得到串S （O(n)） 2.求出后缀数组SA、名次数组Rank （倍增法：O(nlogn) Dc3算法：O(n)） 3.计算height数组并进行标准RMQ方法预处理 （O(n)） 4.枚举i，计算以i为对称中心的极长回文串并更新答案 （O(n)）
我的程序明显写得很~~，Dc3+RMQFast，9k多。 我的程序的整体时间复杂度：O(2n)+O(3*(2n))+O(2n)+O(2n)=O(n)
Test 1: TEST OK [0.022 secs, 14568 KB] Test 2: TEST OK [0.032 secs, 14572 KB] Test 3: TEST OK [0.032 secs, 14572 KB] Test 4: TEST OK [0.022 secs, 14568 KB] Test 5: TEST OK [0.032 secs, 14568 KB] Test 6: TEST OK [0.022 secs, 14568 KB] Test 7: TEST OK [0.022 secs, 14568 KB] Test 8: TEST OK [0.043 secs, 14572 KB]
时间效率的确非常理想。
//By Nettle99 从头开始一个一个找也并非很慢
Test 1: TEST OK [0.000 secs, 3000 KB] Test 2: TEST OK [0.000 secs, 3000 KB] Test 3: TEST OK [0.011 secs, 2996 KB] Test 4: TEST OK [0.011 secs, 2996 KB] Test 5: TEST OK [0.000 secs, 2996 KB] Test 6: TEST OK [0.000 secs, 3000 KB] Test 7: TEST OK [0.011 secs, 2996 KB] Test 8: TEST OK [0.097 secs, 2996 KB]
总时间及内存都要短.也许也只是巧合...
另一种解法:扩展kmp+分治 复杂度: O(nlogn) 效率:
Test 1: TEST OK [0.000 secs, 676 KB] Test 2: TEST OK [0.000 secs, 672 KB] Test 3: TEST OK [0.011 secs, 672 KB] Test 4: TEST OK [0.000 secs, 672 KB] Test 5: TEST OK [0.000 secs, 676 KB] Test 6: TEST OK [0.011 secs, 676 KB] Test 7: TEST OK [0.011 secs, 672 KB] Test 8: TEST OK [0.065 secs, 672 KB]
详见何林的论文<<求最长回文子串与最长重复子串>>及代码3
最后附一下从中间枚举的成绩，感觉程序不是很优秀，但是过没有问题。要是NOI提高组就难讲了。
Test 1: TEST OK [0.000 secs, 260 KB] Test 2: TEST OK [0.000 secs, 264 KB] Test 3: TEST OK [0.000 secs, 260 KB] Test 4: TEST OK [0.000 secs, 260 KB] Test 5: TEST OK [0.000 secs, 264 KB] Test 6: TEST OK [0.000 secs, 264 KB] Test 7: TEST OK [0.011 secs, 264 KB] Test 8: TEST OK [0.184 secs, 264 KB]
All tests OK. 不管怎么说，空间复杂度最低。
后缀数组和RMQ+-1 Executing...
Test 1: TEST OK [0.011 secs, 5432 KB] Test 2: TEST OK [0.011 secs, 5432 KB] Test 3: TEST OK [0.022 secs, 5432 KB] Test 4: TEST OK [0.011 secs, 5432 KB] Test 5: TEST OK [0.022 secs, 5432 KB] Test 6: TEST OK [0.043 secs, 5432 KB] Test 7: TEST OK [0.032 secs, 5432 KB] Test 8: TEST OK [0.108 secs, 5688 KB]
All tests OK.
很慢的说。。。。
我也是从头开始枚举,但是就最后一个数据超时了,郁闷.据说写if句子的顺序很重要，对于数据规模大的题来说，要把最可能的写在前面，可以提高效率。真的是一个个枚举可以吗，是不是有小的技巧或优化？ —— 直接暴力枚举的话也没有多么消耗时空 Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3052 KB] Test 2: TEST OK [0.000 secs, 3052 KB] Test 3: TEST OK [0.000 secs, 3052 KB] Test 4: TEST OK [0.011 secs, 3056 KB] Test 5: TEST OK [0.000 secs, 3052 KB] Test 6: TEST OK [0.011 secs, 3056 KB] Test 7: TEST OK [0.000 secs, 3060 KB] Test 8: TEST OK [0.119 secs, 3056 KB]
从网上查来了一个叫做manacher的O(n)做出最长回文子串的算法,代码简短 就是我看的这个算法的流程只能做出偶数的,所以需要abcba在输入时要处理成aabbccbbaa(即每个字符需要添加一个虚拟的字符) 此算法就不在此赘述了
省去名字..
TASK: calfflac LANG: PASCAL
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 824 KB] Test 2: TEST OK [0.000 secs, 824 KB] Test 3: TEST OK [0.000 secs, 824 KB] Test 4: TEST OK [0.000 secs, 824 KB] Test 5: TEST OK [0.000 secs, 824 KB] Test 6: TEST OK [0.000 secs, 824 KB] Test 7: TEST OK [0.000 secs, 824 KB] Test 8: TEST OK [0.000 secs, 824 KB]
All tests OK.
还有一种方法，直接用简单动规做枚举的限制条件，显然F[i]=F[i-1]+2（a[i]=a[i-f[i-1]-1])如果不能，则再从i-F[i-1] to i搜到相等的判断是否可以构成回文数。 此方法速度极快，而且保证正确。 TASK: calfflac LANG: PASCAL
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 5432 KB] Test 2: TEST OK [0.000 secs, 5432 KB] Test 3: TEST OK [0.000 secs, 5432 KB] Test 4: TEST OK [0.000 secs, 5432 KB] Test 5: TEST OK [0.000 secs, 5432 KB] Test 6: TEST OK [0.000 secs, 5432 KB] Test 7: TEST OK [0.000 secs, 5432 KB] Test 8: TEST OK [0.000 secs, 5432 KB]
All tests OK.
我用的dp（和正常的dp不太一样，dp的思想吧）效率蛮高的 for i:=3 to pp do
begin
if cha[i]=cha[i-1] then f[i]:=i-1;
if cha[i]=cha[f[i-1]-1] then f[i]:=f[i-1]-1;
end;
最长回文就是max{f[i]-i};
测试数据：
USER: fu zhongqing [fuzhong2] TASK: calfflac LANG: PASCAL
Compiling... Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 468 KB] Test 2: TEST OK [0.000 secs, 468 KB] Test 3: TEST OK [0.000 secs, 468 KB] Test 4: TEST OK [0.000 secs, 468 KB] Test 5: TEST OK [0.000 secs, 468 KB] Test 6: TEST OK [0.000 secs, 468 KB] Test 7: TEST OK [0.000 secs, 468 KB] Test 8: TEST OK [0.000 secs, 468 KB]
All tests OK.
yearwhk总是老老实实的遵循KISS原则。考虑到USACO数据一向暴弱，所以，采用枚举中间数的方法+比较危险的优化。即，当奇数回文串找不到时才找偶数回文串： if s=1 then find_even 8个点均秒杀。
Test 1: TEST OK [0.000 secs, 276 KB]
Test 2: TEST OK [0.000 secs, 276 KB]
Test 3: TEST OK [0.000 secs, 276 KB]
Test 4: TEST OK [0.000 secs, 276 KB]
Test 5: TEST OK [0.000 secs, 276 KB]
Test 6: TEST OK [0.000 secs, 276 KB]
Test 7: TEST OK [0.000 secs, 276 KB]
Test 8: TEST OK [0.043 secs, 276 KB] {可能这个算不上秒杀，但也充分体现了这一算法的GOOD。膜拜楼上}
All tests OK.
[编辑] 参考代码
后生插一句：对于回文的题，你们没想到堆栈吗
