淘宝联盟网站推广怎么做,关键词优化计划,网站空间购买多少钱,织梦cms做网站怎么样传送门
题意#xff1a;如果一个字符串可以拆分为AABB的形式#xff0c;其中A和B是任意非空字符串#xff0c;则我们这种拆分是优秀的。求给定串的所有子串的拆分方案数之和。 N≤30000N \leq30000N≤30000
本来是个神仙题
但明明一个O(nlogn)O(nlogn)O(nlogn)的题为啥只…传送门
题意如果一个字符串可以拆分为AABB的形式其中A和B是任意非空字符串则我们这种拆分是优秀的。求给定串的所有子串的拆分方案数之和。
N≤30000N \leq30000N≤30000
本来是个神仙题
但明明一个O(nlogn)O(nlogn)O(nlogn)的题为啥只出300003000030000啊而且只有一个点……搞不懂
显然求出所有位置作为AA的开始和结束位置有多少个然后乘一下加起来
接下来是个神奇做法
枚举我们要求的长度lenlenlen然后每隔lenlenlen记录一个关键点
这样每个长度为2∗len2*len2∗len的AA都恰好经过两个相邻关键点我们用这两个关键点计算贡献。 用后缀数组算出它们向前和向后的最长的相同长度
如果中间没有相交
那么是没有贡献的
如果有相交把相交这段标为蓝色\textcolor{blue}{蓝色}蓝色 我们发现A可以等于蓝色\textcolor{blue}{蓝色}蓝色绿色\textcolor{green}{绿色}绿色紫色\textcolor{purple}{紫色}紫色
挪到后面也可以等于绿色\textcolor{green}{绿色}绿色紫色\textcolor{purple}{紫色}紫色蓝色\textcolor{blue}{蓝色}蓝色
中间随便截一段也是合法的
用个差分即可
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 30005
using namespace std;
typedef long long ll;
int LOG[MAXN];
char s[MAXN];
int n;
struct SuffixArray
{int sa[MAXN],rk[MAXN],tp[MAXN];int c[MAXN],ht[MAXN];int st[MAXN][20];int m;void Rsort(){for (int i1;im;i) c[i]0;for (int i1;in;i) c[rk[i]];for (int i1;im;i) c[i]c[i-1];for (int in;i1;i--) sa[c[rk[tp[i]]]--]tp[i];}void build(){memset(rk,0,sizeof(rk));memset(sa,0,sizeof(sa));memset(tp,0,sizeof(tp));mz;for (int i1;in;i) rk[i]s[i],tp[i]i;Rsort();for (int w1,p0;pn;w1,mp){p0;for (int in-w1;in;i) tp[p]i;for (int i1;in;i) if (sa[i]w) tp[p]sa[i]-w;Rsort();swap(rk,tp);rk[sa[1]]p1;for (int i2;in;i)if (tp[sa[i]]tp[sa[i-1]]tp[sa[i]w]tp[sa[i-1]w]) rk[sa[i]]p;else rk[sa[i]]p;}int k1;for (int i1;in;i){if (k) --k;int jsa[rk[i]-1];while (s[ik]s[jk]) k;ht[rk[i]]k;}memset(st,0,sizeof(st));for (int i1;in;i) st[i][0]ht[i];for (int j1;j20;j)for (int i1;i(1(j-1))n;i)st[i][j]min(st[i][j-1],st[i(1(j-1))][j-1]);}inline int query_st(int l,int r){int tLOG[r-l1];return min(st[l][t],st[r-(1t)1][t]);}inline int query(int x,int y){if (rk[x]rk[y]) swap(x,y);return query_st(rk[x]1,rk[y]);}
}A,B;
#define lcp B.query
#define lcs A.query
int p[MAXN],q[MAXN];
int main()
{LOG[0]-1;for (int i1;iMAXN;i) LOG[i]LOG[i1]1;int T;scanf(%d,T);while (T--){scanf(%s,s1);nstrlen(s1);A.build();reverse(s1,sn1);B.build(); for (int i1;in;i) p[i]q[i]0;for (int len1;lenn;len)for (int ilen;ilenn;ilen){int jilen;int amin(lcp(n-i1,n-j1),len),bmin(lcs(i,j),len);if (ablen) continue;int sab-len-1;p[i-a1];--p[i-as2];q[i-a2*len];--q[i-as2*len1]; }for (int i1;in;i) p[i]p[i-1],q[i]q[i-1];ll ans0;for (int i1;in;i) ans(ll)q[i]*p[i1];printf(%lld\n,ans);}return 0;
}
