Description

給定兩個(gè)字符串，求出在兩個(gè)字符串中各取出一個(gè)子串使得這兩個(gè)子串相同的方案數(shù)。兩個(gè)方案不同當(dāng)且僅當(dāng)這兩 個(gè)子串中有一個(gè)位置不同。

Input

兩行，兩個(gè)字符串s1，s2，長(zhǎng)度分別為n1，n2。1 <=n1, n2<= 200000，字符串中只有小寫字母

Output

輸出一個(gè)整數(shù)表示答案

Sample Input

aabb

bbaa

Sample Output

10

題解

對(duì)這兩個(gè)串建SAM
記錄兩個(gè)right集合right[i][0]和right[i][1]，表示第一個(gè)串，第二個(gè)串在這里的right集合長(zhǎng)度
每個(gè)點(diǎn)的貢獻(xiàn)就是 (tr[i].dep?tr[tr[i].parent].dep)?right[i][0]?right[i][1] ( t r [ i ] . d e p ? t r [ t r [ i ] . p a r e n t ] . d e p ) ? r i g h t [ i ] [ 0 ] ? r i g h t [ i ] [ 1 ]

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define LL long long using namespace std; char ch1[210000],ch2[210000],ch[210000]; struct SAM {int son[30],dep,parent;SAM(){memset(son,0,sizeof(son));} }tr[810000];int root,cnt,last,siz[810000][2]; void add(int x) {int np=++cnt,p=last;tr[np].dep=tr[p].dep+1;while(p&&!tr[p].son[x])tr[p].son[x]=np,p=tr[p].parent;if(p==0)tr[np].parent=root;else{int q=tr[p].son[x];if(tr[q].dep==tr[p].dep+1)tr[np].parent=q;else{int nq=++cnt;tr[nq]=tr[q];tr[nq].dep=tr[p].dep+1;tr[q].parent=tr[np].parent=nq;while(p&&tr[p].son[x]==q)tr[p].son[x]=nq,p=tr[p].parent;}}last=np; } int Rsort[810000],sa[810000]; int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout);root=last=++cnt;scanf("%s",ch+1);int l1=strlen(ch+1);for(int i=1;i<=l1;i++)add(ch[i]-'a'+1),ch1[i]=ch[i];last=root;scanf("%s",ch+1);int l2=strlen(ch+1);for(int i=1;i<=l2;i++)add(ch[i]-'a'+1),ch2[i]=ch[i];for(int i=1;i<=cnt;i++)Rsort[tr[i].dep]++;for(int i=1;i<=l1+l2;i++)Rsort[i]+=Rsort[i-1];for(int i=cnt;i>=1;i--)sa[Rsort[tr[i].dep]--]=i;for(int p=root,i=1;i<=l1;i++){int y=ch1[i]-'a'+1;p=tr[p].son[y];siz[p][0]++;}for(int p=root,i=1;i<=l2;i++){int y=ch2[i]-'a'+1;p=tr[p].son[y];siz[p][1]++;}for(int i=cnt;i>=1;i--)siz[tr[sa[i]].parent][0]+=siz[sa[i]][0],siz[tr[sa[i]].parent][1]+=siz[sa[i]][1];LL ans=0;for(int i=1;i<=cnt;i++)ans+=(LL)(tr[i].dep-tr[tr[i].parent].dep)*siz[i][0]*siz[i][1];printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[bzoj4566][SAM]找相同字符的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。