石家庄网站建设德信互联科技有限公司,个人网页设计作品展示,安徽论坛网站建设,做问卷的网站有那些正题
题目链接:https://www.luogu.com.cn/problem/P1117 题目大意
长度为nnn的字符串#xff0c;求所有子串有多少种分割成AABBAABBAABB的方式。 解题思路 aia_iai表示以iii结尾的子串中有多少种分割成AAAAAA的方式 bib_ibi表示以iii开头的子串中有多少种分割成AAAAAA的…正题
题目链接:https://www.luogu.com.cn/problem/P1117 题目大意
长度为nnn的字符串求所有子串有多少种分割成AABBAABBAABB的方式。 解题思路
aia_iai表示以iii结尾的子串中有多少种分割成AAAAAA的方式 bib_ibi表示以iii开头的子串中有多少种分割成AAAAAA的方式
然后答案就是∑i1n−1aibi1\sum_{i1}^{n-1}a_ib_{i1}i1∑n−1aibi1
考虑用SASASA来计算a,ba,ba,b。
枚举长度lenlenlen考虑所有长度为2∗len2*len2∗len的AAAAAA串我们没隔lenlenlen格放置一个点那么每个串必定经过了两个点现在考虑求出相邻两个点之间的贡献
对于相邻两个点l,rl,rl,r求出它们的LCPLCPLCP和LCSLCSLCS分情况讨论
LCPLCSlen:LCPLCSlen:LCPLCSlen:那么我们可以发现没有任何一个串2∗len2*len2∗len的AAAAAA串同时经过这两个点因为在lll的右边和rrr的左边这两个串必定有一个地方不同。LCPLCS≥len:LCPLCS\geq len:LCPLCS≥len:那么此时有串经过这两个点且 s≥l−LCP1,t≤rLCPs\geq l-LCP1,t\leq rLCPs≥l−LCP1,t≤rLCP的串都满足条件
时间复杂度:O(nlogn):O(n\log n):O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2e510;
int T,n;
long long ans,a[N],b[N];
struct SA{char s[N];int m,sa[N],rk[N],height[N],lg[N];int c[N],x[N],y[N],st[N][25];void Qsort(){for(int i1;im;i) c[i]0;for(int i1;in;i) c[x[i]];for(int i1;im;i) c[i]c[i-1];for(int in;i1;i--) sa[c[x[y[i]]]--]y[i],y[i]0;return;}void Get_SA(){m256;for(int i1;in;i)x[i]s[i],y[i]i;Qsort();for(int w1;wn;w1){int p0;for(int in-w1;in;i) y[p]i;for(int i1;in;i)if(sa[i]w) y[p]sa[i]-w;Qsort();swap(x,y);x[sa[1]]p1;for(int i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]w]y[sa[i-1]w])?p:p;if(pn) break;mp;}return;}void Get_Height(){int k0;for(int i1;in;i)rk[sa[i]]i;for(int i1;in;i){if(rk[i]1) continue;if(k)k--;int jsa[rk[i]-1];while(iknjkns[ik]s[jk]) k;height[rk[i]]k;}return;}void Get_ST(){lg[0]-1;for(int i1;in;i)lg[i]lg[i1]1,st[i][0]height[i];for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i)st[i][j]min(st[i(1(j-1))][j-1],st[i][j-1]);return;}void Build(){memset(rk,0,sizeof(rk));memset(st,0,sizeof(st));memset(height,0,sizeof(height));memset(sa,0,sizeof(sa));memset(x,0,sizeof(x));memset(y,0,sizeof(y));Get_SA();Get_Height();Get_ST();return;}int LCP(int l,int r){lrk[l];rrk[r];if(lr) swap(l,r);l;int zlg[r-l1];return min(st[l][z],st[r1-(1z)][z]);}
}s1,s2;
int main()
{scanf(%d,T);while(T--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));scanf(%s,s1.s1);nstrlen(s1.s1);for(int i1;in;i)s2.s[n-i1]s1.s[i];s1.Build();s2.Build();for(int len1;lenn/2;len){for(int ilen;in;ilen){int li,rilen;int Ln-r2,Rn-l2;int lcpmin(len,s1.LCP(l,r));int lcsmin(len-1,s2.LCP(L,R));if(lcplcslen){b[l-lcs];b[llcp-len1]--;a[rlcp]--;a[r-lcslen-1];}}}ans0;for(int i1;in;i){a[i]a[i-1],b[i]b[i-1];ansa[i-1]*b[i];}printf(%lld\n,ans);}return 0;
}
