[問題] Manacher 演算法 求最長回文字串

[DiLegend (JOU)]

這幾天都再研究這個算法
算法本身好像懂又好像不懂

實際測試後
忽然注意到一點

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看 跑到可能會錯誤時 到這句就直接跳過


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.149.112
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1430832746.A.A8E.html
※ 編輯: DiLegend (36.228.149.112), 05/05/2015 21:32:58
→ scwg: 運氣好 str[-1] 可以讀? 演算法 MIN 取左邊時要跳過那個for
推 yvb: google 了一下, 那個 str 跟輸入內容不同, 已經被轉換過了.
→ yvb: 比方輸入為 "abcd", 則 str 為 "$#a#b#c#d#"
→ DiLegend: 對會轉成那樣 我這幾天再想 aaaaa  轉成$#a#a#a#a#a#
→ DiLegend: 算到第4個a時 為何不會str[i+p[i]] str[8+4] 然後爆了
推 yvb: ??? str[8+4] => '\0', str[8-4] => 'a', for 就跳出了...
→ DiLegend: str=[$#a#a#a#a#a#] str[0~11] str[12]不就超出了
→ DiLegend: 哪來的 '\0' 啊
→ scwg: C 的字串一律用 '\0' 字元標記結束. 寫 "abc" 實際上有四個
→ scwg: 字元: 'a' 'b' 'c' '\0'
推 yvb: 這實作還是小有問題. 若輸入為 "$", 會發生 str[-1] 的情況.
→ scwg: 題目在 http://poj.org/problem?id=3974 只有小寫字母
推 yvb: 說得也是. 按其說明, '$'和'#' 實際上是選取不會出現的字符.