YZOJ P3939 [HAOI2016]找相同字符
时间限制:1000MS 内存限制:262144K
难度:\(6.5\)
-
题目描述
给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。
两个方案不同当且仅当这两个子串中有一个位置不同。
-
输入格式
两行,两个字符串 \(s_1, s_2\),\(1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000\),字符串中只有小写字母。
-
输出格式
输出一个整数表示答案
-
样例输入
1 2 |
aabb bbaa |
-
样例输出
1 |
10 |
Source: BZOJ 4566
广义SAM 或者 在SAM上跑匹配 都能做。
比如建立 广义SAM,处理出每个节点的 \(right_1, right_2\) 集合的大小,然后答案就是 \(\sum\limits_{x}{\left(max_x-min_x+1\right) \times \left|right_1\right| \times \left|right_2\right|}\) 。
跑匹配的话有点复杂。
首先对 \(s_1\) 建立SAM,\(s_2\) 放在上面跑匹配,失配了就通过 parent
跳回去。
注意到若匹配到这一节点时已经匹配的长度为 \(len\) ,那么长度 \(\leq len\) 的字符串(为当前字符串的后缀)也都已经被匹配,即这个节点沿着 parent
树向上的所有节点都被匹配了。
所以按照拓扑序预处理每个节点完全被匹配对答案的贡献 \(ans\),即通过 parent
树关系向下贡献,有 \(ans_x=ans_{parent_x}+\left(max_x-min_x+1\right) \times \left|right\right|\) 。
匹配到节点 \(x\) ,已经匹配的长度为 \(len\),那么其对答案的贡献为 \(ans_{parent_x}+\left(len-min_x+1\right) \times \left|right\right|\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> inline void getstr(char s[],int&ls) { register char c=0; while(!(c>='a' && c<='z')) c=getchar(); ls=0; while(c>='a' && c<='z') s[++ls]=c,c=getchar(); s[ls+1]=0; return; } #define CHARSET 26 char x[205050],y[205050]; int cnt,parent[405050],mxval[405050],ch[405050][CHARSET],last; int right[405050]; inline int CreateNode(register int val=0) { cnt++,parent[cnt]=0,mxval[cnt]=val; for(register int j=0;j<CHARSET;j++) ch[cnt][j]=0; return cnt; } inline int ExtendNode(register short c) { register int now=last,nw=CreateNode(mxval[last]+1); right[nw]=1; for(; now && !ch[now][c]; now=parent[now]) ch[now][c]=nw; if(!now) return parent[nw]=1,last=nw; register int q=ch[now][c]; if(mxval[q] == mxval[now]+1) return parent[nw]=q,last=nw; register int b=CreateNode(mxval[now]+1); for(register int j=0;j<CHARSET;j++) ch[b][j]=ch[q][j]; parent[b]=parent[q],parent[q]=parent[nw]=b; for(; now && ch[now][c]==q; now=parent[now]) ch[now][c]=b; return last=nw; } long long ansum[405050],ans; int bucket[405050],lst[405050]; inline void TopoSort() { for(register int i=1;i<=cnt;i++) bucket[mxval[i]]++; for(register int i=1;i<=cnt;i++) bucket[i]+=bucket[i-1]; for(register int i=1;i<=cnt;i++) lst[bucket[mxval[i]]--]=i; for(register int i=cnt;i>=1;i--) right[parent[lst[i]]]+=right[lst[i]]; for(register int i=2;i<=cnt;i++) for(register int j=0;j<CHARSET;j++) if(ch[lst[i]][j]) ansum[lst[i]]=ansum[parent[lst[i]]] \ +(long long)right[lst[i]]*(mxval[lst[i]]-mxval[parent[lst[i]]]); } int main() { int lx;getstr(x,lx); int ly;getstr(y,ly); last=CreateNode(); for(register int i=1;i<=lx;i++) ExtendNode(x[i]-'a'); TopoSort(); register int now=1,len=0; for(register int i=1;i<=ly;i++) { register short c=y[i]-'a'; if(ch[now][c]) len++,now=ch[now][c]; else { while(now && !ch[now][c]) now=parent[now]; if(!now) now=1,len=0; else len=mxval[now]+1,now=ch[now][c]; } ans+=ansum[parent[now]]+(long long)right[now]*(len-mxval[parent[now]]); } printf("%lld\n",ans); return 0; } |