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

看板C_and_CPP作者 (JOU)時間10年前 (2015/05/05 21:32), 10年前編輯推噓4(4推 0噓 9→)
留言13則, 3人參與, 最新討論串1/1
這幾天都再研究這個算法 算法本身好像懂又好像不懂 實際測試後 忽然注意到一點 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
→
05/05 21:43, , 1F
運氣好 str[-1] 可以讀? 演算法 MIN 取左邊時要跳過那個for
05/05 21:43, 1F
推
05/05 21:56, , 2F
google 了一下, 那個 str 跟輸入內容不同, 已經被轉換過了.
05/05 21:56, 2F
→
05/05 21:59, , 3F
比方輸入為 "abcd", 則 str 為 "$#a#b#c#d#"
05/05 21:59, 3F
→
05/05 22:11, , 4F
對會轉成那樣 我這幾天再想 aaaaa 轉成$#a#a#a#a#a#
05/05 22:11, 4F
→
05/05 22:15, , 5F
算到第4個a時 為何不會str[i+p[i]] str[8+4] 然後爆了
05/05 22:15, 5F
推
05/05 22:28, , 6F
??? str[8+4] => '\0', str[8-4] => 'a', for 就跳出了...
05/05 22:28, 6F
→
05/06 09:47, , 7F
str=[$#a#a#a#a#a#] str[0~11] str[12]不就超出了
05/06 09:47, 7F
→
05/06 09:47, , 8F
哪來的 '\0' 啊
05/06 09:47, 8F
→
05/06 10:02, , 9F
C 的字串一律用 '\0' 字元標記結束. 寫 "abc" 實際上有四個
05/06 10:02, 9F
→
05/06 10:02, , 10F
字元: 'a' 'b' 'c' '\0'
05/06 10:02, 10F
推
05/06 21:08, , 11F
這實作還是小有問題. 若輸入為 "$", 會發生 str[-1] 的情況.
05/06 21:08, 11F
→
05/07 00:29, , 12F
題目在 http://poj.org/problem?id=3974 只有小寫字母
05/07 00:29, 12F
推
05/07 14:13, , 13F
說得也是. 按其說明, '$'和'#' 實際上是選取不會出現的字符.
05/07 14:13, 13F
‣ 更多 DiLegend 的文章
文章代碼(AID): #1LICPggE (C_and_CPP)