啊宝贝才几天没做网站,科技酒店,seo流量工具,照片制作小视频ACM模板 目录KMP字符串Fail失配树KMP字符串
肖然大佬视频讲解 子串#xff1a; 从原串中选取连续的一段#xff0c;即为子串#xff08;包括空串#xff09; 前缀#xff1a; pre(s,k)pre(s,k)pre(s,k) 为 s 前 k 个字符构成的子串 后缀#xff1a; suf(s,k)suf(s,k)suf…ACM模板 目录KMP字符串Fail失配树KMP字符串
肖然大佬视频讲解 子串 从原串中选取连续的一段即为子串包括空串 前缀 pre(s,k)pre(s,k)pre(s,k) 为 s 前 k 个字符构成的子串 后缀 suf(s,k)suf(s,k)suf(s,k) 为 s(k…n) 构成的子串 任何子串都是某个后缀的前缀 最长公共前缀 lcp(s,t)lcp(s,t)lcp(s,t) 和最长公共后缀 lcs(s,t)lcs(s,t)lcs(s,t) 周期 ①0p∣s∣0p|s|0p∣s∣ ②s[i]s[ip],∀i∈{1,2,…,∣s∣−p}s[i]s[ip], \forall i\in\{1,2,\dots,|s|-p\}s[i]s[ip],∀i∈{1,2,…,∣s∣−p}满足以上条件称 ppp为 s 的周期 Border ①0r∣s∣0r|s|0r∣s∣ ②pre(s,r)suf(s,r)pre(s,r)suf(s,r)pre(s,r)suf(s,r)满足以上条件称 pre(s,r)pre(s,r)pre(s,r)为 s 的 border 周期与Border的关系pre(s,k)pre(s,k)pre(s,k)是 s 的 border ⇔\Leftrightarrow⇔ ∣s∣−k|s|-k∣s∣−k 是 s 的周期 Border的传递性 ①串 s 是 t 的 border 串 t 是 r 的 border那么 s 是 r 的border ②串 s 是 r 的 border串 t ∣t∣∣s∣|t||s|∣t∣∣s∣也是 r 的 border则 s 是 t 的border 记 mb(s) 表示 s 的最长 border 则 mb(s)mb(mb(s))…构成 s 的所有 border 给定一个模式串S以及一个模板串P所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标0开始。
#includeiostream
using namespace std;
const int N1000010;
int n,m;
char p[N],s[N];
int ne[N];
int main()
{cinnp1ms1;// 求ne过程看成两个相同的串匹配for(int i2,j0;in;i){while(jp[i]!p[j1]) jne[j];if(p[i]p[j1]) j;// i结尾能够匹配 1~j 那么ne[i]jne[i]j;}// 当前需要判断是否匹配 p[j1]?s[i]for(int i1,j0;im;i){while(js[i]!p[j1]) jne[j];if(s[i]p[j1]) j;if(jn){couti-n ;jne[j];}}return 0;
}Fail失配树
概念以及构造 将 next[i] 视为 i 点的父节点那么通过 next 数组可以把 0~N 点连成一棵树满足性质
点 i 的所有祖先都是前缀 pre(s,i) 的 border没有祖先关系的两个点 ij 没有 border 关系
联系 计算 next[i] 的过程可以看作从 jfa[i-1] 开始不断往上走找到第一个满足 s[j1]s[i] 的点把点 i 的父亲设为 j1
#includestring
#includeiostream
using namespace std;
const int N1000010;
int ne[N];
int fa[N][21],dep[N];
string s;
int n;
int lca(int a,int b)
{if(dep[a]dep[b]) swap(a,b);for(int k20;k0;k--)if(dep[fa[a][k]]dep[b]) afa[a][k];if(ab) return a;for(int k20;k0;k--)if(fa[a][k]!fa[b][k]){afa[a][k];bfa[b][k];}return fa[a][0];
}
int main()
{cins;ns.size();s.s;dep[0]1,dep[1]2;fa[1][0]0;for(int i2,j0;in;i){while(js[i]!s[j1]) jne[j];if(s[i]s[j1]) j;ne[i]j;// 构建失配树fa[i][0]j;dep[i]dep[j]1;for(int k1;k20;k)fa[i][k]fa[fa[i][k-1]][k-1];}int q;cinq;while(q--){int a,b;cinab;int pablca(a,b);// 注意本身是公共祖先的情况if(apab||bpab) coutne[pab]\n;else coutpab\n;}return 0;
}
