這幾天都再研究這個算法
算法本身好像懂又好像不懂
實際測試後
忽然注意到一點
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 只有小寫字母

說得也是. 按其說明, '$'和'#' 實際上是選取不會出現的字符.