字符串优化
字符串问题
\(\mathcal O(nm)-\mathcal O(1)\) 比较字符串子串大小
令 \(lcp_{x,y}=\operatorname{lcp}(s[x\sim n],s[y\sim n])\)，有
\[lcp_{x,y}=
\left\{\begin{aligned}
&lcp_{x+1,y+1}+1&&s_x=s_y\\
&0&&s_x\not=s_y
\end{aligned}\right.
\]
可以 \(\mathcal O(n^2)\) 求出。
比较两个子串 \(s[l_1\sim r_1]\) 与 \(s[l_2\sim r_2]\)。
-
若 \(lcp_{l_1,l_2}\ge \min(r_1-l_1+1,r_2-l_2+1)\)，直接比较子串长度。
-
否则比较 \(s[l_1+lcp_{l_1,r_1}]\) 与 \(s[l_2+lcp_{l_1,l_2}]\)
代码如下：
bool cmp(pa a,pa b){
int lena=a.r-a.l+1,lenb=b.r-b.l+1,LCP=lcp[a.l][b.l];
if(LCP>=lena||LCP>=lenb)return lena<lenb;
return s[a.l+LCP]<s[b.l+LCP];
}
01串相同长度汉明距离
Q:求01串A的所有长度与01串B相同的子串的汉明距离
我们考虑算卷积，将 \(B\) 翻转并在后面加 \(0\) ，\(S\) 卷积相乘。
结果的第 \(P\) 位的值为 \(\sum_{j=0}^PB_jA_{P-j}=k\) ，对于只有 01 的串，只有 \(1\times 1=1\) ，因此 \(k\) 代表 \(B_j\) 同 \(A_{P-j}\) 中有多少位同时是 \(1\)，也就是说串 \(B_0\) 到 \(B_P\)，与串 \(A_P\) 到 \(A_0\) 中 \(1\) 的匹配数量。如果利用 \(FFT\) 算卷积，则是 \(\mathcal O(n\log n)\) 的 。
同样，我们将 \(0\) 换成 \(1\) ，\(1\) 换成 \(0\)，再做一次卷积，这样可以求出有多少 \(0\) 和 \(0\) 是匹配的。
最后用 \(|B|\) 减去所有匹配中的最大值即可。