扩展KMP

优质博客推荐 问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。 求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。 我们直接讨论在中间时匹配的情况。 已知: …

LCA倍增

优质博客推荐 hdu6115 #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<map> #include<vector> using namespace std; const int inf=0x3f3f3f3f; #define mem(a …

tarjan算法之桥

博客推荐 与割点的最大不同之处:low[v]>low[u] 易错点: 1.父亲节点与子节点区别一下,防止两个点误认为环。 2.去重边 #include<stdio.h> #include<string.h> #include<string> #include<iostream> #includ …