昨天參加了某公司的校園招聘的筆試題，做得慘不忍睹，其中就有這么一道算法設(shè)計(jì)題：求一個(gè)字符串的最長(zhǎng)回文字串。我在ACM校隊(duì)選拔賽上遇到過(guò)這道題，當(dāng)時(shí)用的后綴數(shù)組AC的，但是模板忘了沒(méi)寫出代碼來(lái)。

　　回頭我把這道題目再次問(wèn)了隊(duì)友，他搞字符串的，說(shuō)后綴數(shù)組求最長(zhǎng)回文串是nlogn的，這個(gè)logn要大也大不到哪里去，所以這個(gè)做法可以過(guò)一般的題目的，但是他告訴我有O(n)的算法——manacher算法，當(dāng)時(shí)我就驚呆了，估計(jì)筆試得掛了。

　　回頭做了HDU3068，從這道題學(xué)會(huì)了manacher算法。

　　manacher算法資料請(qǐng)戳：http://pan.baidu.com/s/1dzWJq

轉(zhuǎn)載于:https://www.cnblogs.com/huangfeihome/p/3346428.html

總結(jié)

以上是生活随笔為你收集整理的求字符串的最长回文字串 O(n)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。