德州网站建设维护,网站排行榜查询,百度推广怎么开户,wordpress 开发飞猪接口前置知识#xff1a;基本子串结构#xff0c;SAM的结构和应用
学长博客
字符串理论比较抽象#xff0c;建议直观的去理解它
子串 t t t的扩展串定义为 ext(t) : t ′ \text{ext(t)}:t ext(t):t′#xff0c;满足 t t t是 t ′ t t′的子串#xff0c;且 occ(t) occ(t…前置知识基本子串结构SAM的结构和应用
学长博客
字符串理论比较抽象建议直观的去理解它
子串 t t t的扩展串定义为 ext(t) : t ′ \text{ext(t)}:t ext(t):t′满足 t t t是 t ′ t t′的子串且 occ(t) occ(t’) \text{occ(t)}\text{occ(t)} occ(t)occ(t’)
基本性质若 t [ l : r ] , t ′ [ l ′ : r ′ ] t[l:r],t[l:r] t[l:r],t′[l′:r′] t ′ ′ [ l ′ ′ : r ′ ′ ] t[l:r] t′′[l′′:r′′]使得 l ′ ≤ l ′ ′ ≤ l ≤ r ≤ r ′ ′ ≤ r ′ l\le l\le l\le r\le r\le r l′≤l′′≤l≤r≤r′′≤r′则 ext(t”) t ′ \text{ext(t)}t ext(t”)t′
子串 x , y x,y x,y等价当且仅当 ext(x) ext(y) \text{ext(x)}\text{ext(y)} ext(x)ext(y)。然后记录每个等价类的最长串作为代表元。
在 s [ l : r ] ↦ ( l , r ) s[l:r]\mapsto (l,r) s[l:r]↦(l,r)的作用下在 y x yx yx以上的点被等价类划分入若干个阶梯状集合其中 g \text{g} g对应的阶梯 出现次数 为 occ(rep(g)) \text{occ(\text{rep(g)})} occ(rep(g))。
对于等价类 g g g个某个 完整阶梯其完整的一行对应的子串集合与 T 0 T_0 T0的某个结点对应的子串集合相同其完整的一列对应的子串集合与 T 1 T_1 T1反串对应的后缀树某个节点对应的子串集合相同并且一一对应。
定义等价类 g g g的周长为其 一个 完整阶梯的行数列数之和性质 ∑ g per(g) O ( n ) \sum_g\text{per(g)}O(n) ∑gper(g)O(n)
比较抽象。不是很直观。
如何显式求出这个结构
第一种方式对于 T 0 T_0 T0的从父亲到儿子的树边其从一行的左边界指向另一行的右边界对于 T 1 T_1 T1的从父亲到儿子的树边其从一行的上边界连向另一行的下边界。
例如 s aababcd ‾ s\underline{\text{aababcd}} saababcd其对应的阶梯划分为 其对应的 S A M SAM SAM和 T 0 T_0 T0为 其对应的连边为 第二种方式感觉更常用对于 D A G DAG DAG上的一条边 ( u , v ) (u,v) (u,v)如果 occ(u) occ(v) \text{occ(u)}\text{occ(v)} occ(u)occ(v)那么就将这条边标记为关键边。
性质如果只保留关键边那么每个点入度和出度都至多为一因此我们得到了若干条关键链。显然链的末尾就是代表元一条链就代表了一个等价类
考虑这道题目在让我们干什么可以发现一个字符串对 ( b 1 , b 2 ) (b_1,b_2) (b1,b2)是好的当且仅当满足以下条件 1.1 1.1 1.1 b 1 , b 2 b_1,b_2 b1,b2在同一个等价类中 1.2 1.2 1.2 设 b 1 , b 2 b_1,b_2 b1,b2所在等价类中的代表元为 b b b那么 b 1 , b 2 b_1,b_2 b1,b2在 b b b中出现的位置不交且 b 1 b_1 b1在 b 2 b_2 b2左边
这样我们对于每个 阶梯状物 统计答案即可。建议数形结合以及把下标搞清楚
代表元的 len \text{len} len实际上表示阶梯状物左上角那个位置的横纵坐标之差。
复杂度 O ( n ) O(n) O(n)。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N2e55;
struct node{int to[26],link,len,sz;
}t[N];
int n,cur,last,tot,sz[N];
void extend(int ch){int curtot;t[cur].lent[last].len1,t[cur].sz1;int plast;while(p!-1!t[p].to[ch]){t[p].to[ch]cur;pt[p].link;}if(p!-1){int qt[p].to[ch];if(t[q].lent[p].len1){t[cur].linkq;}else{int clonetot;t[clone].linkt[q].link;for(int i0;i26;i)t[clone].to[i]t[q].to[i];t[clone].lent[p].len1;while(p!-1t[p].to[ch]q){t[p].to[ch]clone;pt[p].link;}t[q].linkt[cur].linkclone;}}lastcur;
}
string str;
int nxt[N],vs[N];
int st[N],cnt;
ll s[N];
ll res;
vectorintG[N];
void dfs(int u){for(auto v:G[u])dfs(v),t[u].szt[v].sz;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);t[0].link-1;cinstr,nstr.size();for(int i0;in;i)extend(str[i]-a);for(int i1;itot;i)G[t[i].link].pb(i);dfs(0);for(int i1;itot;i){for(int j0;j26;j){int kt[i].to[j];if(kt[i].szt[k].sz)nxt[i]k,vs[k]1;}}for(int i1;itot;i){if(vs[i]0){cnt0;int e0;for(int ji;j;jnxt[j])ej,st[cnt]t[j].len-t[t[j].link].len;for(int j1;jcnt;j)s[j]s[j-1]st[j];int p1,lent[e].len;for(int jlen-cnt1;jst[cnt]jlen1;j){while(pcntst[p]j)p;ress[cnt-lenj-1]*(cnt-p1);}}}coutres;
}
