这几天都再研究这个算法
算法本身好像懂又好像不懂
实际测试后
忽然注意到一点
void pk()
{
int i;
int mx = 0;
int id;
for(i=1; i<n; i++)
{
if( mx > i )
p[i] = MIN( p[2*id-i], mx-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
if( p[i] + i > mx )
{
mx = p[i] + i;
id = i;
}
}
}
for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
;
我不懂这句为什么不会造成内存问题
实际debug看 跑到可能会错误时 到这句就直接跳过

运气好 str[-1] 可以读? 算法 MIN 取左边时要跳过那个for

google 了一下, 那个 str 跟输入内容不同, 已经被转换过了.比方输入为 "abcd", 则 str 为 "$#a#b#c#d#"

对会转成那样 我这几天再想 aaaaa 转成$#a#a#a#a#a#算到第4个a时 为何不会str[i+p[i]] str[8+4] 然后爆了

??? str[8+4] => '\0', str[8-4] => 'a', for 就跳出了...

str=[$#a#a#a#a#a#] str[0~11] str[12]不就超出了哪来的 '\0' 啊

C 的字串一律用 '\0' 字符标记结束. 写 "abc" 实际上有四个字符: 'a' 'b' 'c' '\0'

这实作还是小有问题. 若输入为 "$", 会发生 str[-1] 的情况.

题目在 http://poj.org/problem?id=3974 只有小写字母

说得也是. 按其说明, '$'和'#' 实际上是选取不会出现的字符.