XSY3320

前置芝士：回文前綴&&$border$
推薦博客
推薦博客

考慮點分治，問題變成求經(jīng)過重心的回文路徑個數(shù)。
一條經(jīng)過重心的回文路徑長這樣：

$x$到$z$的串與$y$到$root$的串相同。

建出根到每個節(jié)點對應的串的AC自動機，并在$fail$樹上找出每個串的回文前綴。判斷根到某個節(jié)點對應的串是不是回文串可以用哈希解決。

根據(jù)$border$理論，一個回文串的所有回文前綴的長度可以組成一個不超過$O(logn)$項的等差數(shù)列。即若$T_k$是回文串，$T_k$的最長回文真前綴是$T_{k?1}$，$T_{k?1}$的最長回文真前綴是$T_{k?2}$，…，$T_2$的最長回文真前綴是$T_1$，那么有$|T_i|=|T_{i?1}|+d$（$d$為公差）。

考慮一個點作為$x$的貢獻。設根到$x$對應的串為$U$，$U$在AC自動機上對應點$X$。把$U$的最長回文真前綴看成$T_k$，那么$T_i$作為回文串$T$時，我們要查詢有多少個點$y$，滿足根到$y$對應的串是$U$的后綴，且長度為$|U|?|T_i|=|U|?|T_1|?(i?1)d$，記有$num[i]$個符合條件的$y$。那么最后這個$x$的貢獻就是${\sum }_{i=1}^{k}num[i]$，換句話說，我們要求有多少個點$y$，滿足根到$y$對應的串是$U$的后綴，且長度$len$符合：$len\equiv |U|?|T_1|(\mathrm{m}\mathrm{o}\mathrm{d}d),|U?T_1|\le len\le |U|?|T_k|$。

$U$的后綴，即$X$在$fail$樹上的祖先對應的串。我們對$fail$樹$dfs$，同時開一個數(shù)組$c_{i,j}$ 記錄當前節(jié)點有多少個祖先（包括自己），滿足該祖先代表的串的長度 $\mathrm{m}\mathrm{o}\mathrm{d}i=j$。

那么最終貢獻就是$dfs$到的點代表的串長為$|U|?|T_k|$時$c_{d,(|U|?|T_1|)\mathrm{m}\mathrm{o}\mathrm{d}d}$的值 減去 $dfs$到的點代表的串長為$|U|?|T_1|?d$時$c_{d,(|U|?|T_1|)\mathrm{m}\mathrm{o}\mathrm{d}d}$的值。

但這樣空間復雜度是$O(n^2)$的，所以我們考慮分塊，只開到$c[\sqrt{n}][\sqrt{n}]$的大小，對于公差大于$\sqrt{n}$的，我們暴力跳$fail$尋找答案。

總結

以上是生活随笔為你收集整理的[XSY3320] string （AC自动机，哈希，点分治）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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