多用户商城网站建设,全国中高风险地区一览,gta手机网站大全,上海网站建设公司页溪网络所谓拓展kmp#xff0c;就是拓展的kmp #xff08;逃#xff09;
前言
小清新算法#xff0c;更像一个trick。 exkmp能够在线性复杂度内求出字符串所有后缀与字符串本身的lcp。 个人感觉这个东西和kmp关系不大#xff0c;反而有些像马拉车的思想。 之前学的东西#xf… 所谓拓展kmp就是拓展的kmp 逃
前言
小清新算法更像一个trick。 exkmp能够在线性复杂度内求出字符串所有后缀与字符串本身的lcp。 个人感觉这个东西和kmp关系不大反而有些像马拉车的思想。 之前学的东西现在才想起来写一个解析。
解析
定义 ziz_izi 表示字符串的后缀 iii 与开头的lcp。 考虑在求完 z1...i−1z_{1...i-1}z1...i−1 的情况下如何求解 ziz_izi。 设 pospospos 为满足 poszposposz_{pos}poszpos 最大的位置rposzpos−1rposz_{pos}-1rposzpos−1。 分情况讨论
iririr暴力算出 ziz_izi并使 pos←ipos\gets ipos←i。i≤ri\le ri≤r此时在 rrr 左侧 iii 的 lcp 情况与 i−pos1i-pos1i−pos1 是相同的所以先令 zi←min(r−i1,zi−pos1)z_i\gets \min(r-i1,z_{i-pos1})zi←min(r−i1,zi−pos1)如果这个 min\minmin 取的是前一项就再暴力尝试拓展 ziz_izi。
和马拉车类似的当我们暴力计算 ziz_izi 而产生复杂度时都必然伴随着 rrr 的增大rrr 最多不会超过 nnn所以均摊总复杂度为 O(n)O(n)O(n)。
代码
void exkmp(){z[1]0;int pl0;for(int i2;in;i){if(iplz[pl]-1){while(s[1z[i]]s[iz[i]]) z[i];}else{z[i]min(plz[pl]-i,z[i-pl1]);if(z[i]plz[pl]-i){while(s[1z[i]]s[iz[i]]) z[i];} }if(iz[i]plz[pl]) pli;}return;
}
