但是关于回文串的信息可用 一种更紧凑的方式 表达:对于每个位置 i = 0 \dots n - 1,我们找出值 d_1[i] 和 d_2[i]。二者分别表示以位置 i 为中心的长度为奇数和长度为偶数的回文串个数。换个角度,二者也表示了以位置 i 为中心的最长回文串的半径长度(半径长度 d_1[i],d_2[i] 均为从位置 i 到回文串最右端位置包含的字符个数)。
举例来说,字符串 s = \mathtt{abababc} 以 s[3] = b 为中心有三个奇数长度的回文串,最长回文串半径为 3,也即 d_1[3] = 3:
a\ \overbrace{b\ a\ \underset{s_3}{b}\ a\ b}^{d_1[3]=3}\ c
字符串 s = \mathtt{cbaabd} 以 s[3] = a 为中心有两个偶数长度的回文串,最长回文串半径为 2,也即 d_2[3] = 2:
c\ \overbrace{b\ a\ \underset{s_3}{a}\ b}^{d_2[3]=2}\ d
因此关键思路是,如果以某个位置 i 为中心,我们有一个长度为 l 的回文串,那么我们有以 i 为中心的长度为 l - 2,l - 4,等等的回文串。所以 d_1[i] 和 d_2[i] 两个数组已经足够表示字符串中所有子回文串的信息。
// C++ Versionvector<int>d1(n),d2(n);for(inti=0;i<n;i++){d1[i]=1;while(0<=i-d1[i]&&i+d1[i]<n&&s[i-d1[i]]==s[i+d1[i]]){d1[i]++;}d2[i]=0;while(0<=i-d2[i]-1&&i+d2[i]<n&&s[i-d2[i]-1]==s[i+d2[i]]){d2[i]++;}}
// C++ Versionvector<int>d1(n);for(inti=0,l=0,r=-1;i<n;i++){intk=(i>r)?1:min(d1[l+r-i],r-i+1);while(0<=i-k&&i+k<n&&s[i-k]==s[i+k]){k++;}d1[i]=k--;if(i+k>r){l=i-k;r=i+k;}}
// C++ Versionvector<int>d2(n);for(inti=0,l=0,r=-1;i<n;i++){intk=(i>r)?0:min(d2[l+r-i+1],r-i+1);while(0<=i-k-1&&i+k<n&&s[i-k-1]==s[i+k]){k++;}d2[i]=k--;if(i+k>r){l=i-k-1;r=i+k;}}
给定一个长度为 n 的字符串 s,我们在其 n + 1 个空中插入分隔符 \#,从而构造一个长度为 2n + 1 的字符串 s'。举例来说,对于字符串 s = \mathtt{abababc},其对应的 s' = \mathtt{\#a\#b\#a\#b\#a\#b\#c\#}。
对于字母间的 \#,其实际意义为 s 中对应的“空”。而两端的 \# 则是为了实现的方便。
注意到,在对 s' 计算 d_1[] 后,对于一个位置 i,d_1[i] 所描述的最长的子回文串必定以 \# 结尾(若以字母结尾,由于字母两侧必定各有一个 \#,因此可向外扩展一个得到一个更长的)。因此,对于 s 中一个以字母为中心的极大子回文串,设其长度为 m + 1,则其在 s' 中对应一个以相应字母为中心,长度为 2m + 3 的极大子回文串;而对于 s 中一个以空为中心的极大子回文串,设其长度为 m,则其在 s' 中对应一个以相应表示空的 \# 为中心,长度为 2m + 1 的极大子回文串(上述两种情况下的 m 均为偶数,但该性质成立与否并不影响结论)。综合以上观察及少许计算后易得,在 s' 中,d_1[i] 表示在 s 中以对应位置为中心的极大子回文串的 总长度加一。
上述结论建立了 s' 的 d_1[] 同 s 的 d_1[] 和 d_2[] 间的关系。
由于该统一处理本质上即求 s' 的 d_1[],因此在得到 s' 后,代码同上节计算 d_1[] 的一样。