题目描述
如果一个字符串可以被拆分为的形式,其中
和
是任意非空字符串,则我们称该字符串的这种拆分是优秀的。
例如,对于字符串,如果令
,
,我们就找到了这个字符串拆分成
的一种方式。
一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令,
,也可以用
表示出上述字符串;但是,字符串
就没有优秀的拆分。
现在给出一个长度为的字符串
,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意:
出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
在一个拆分中,允许出现。例如
存在拆分
。
字符串本身也是它的一个子串。
输入格式
每个输入文件包含多组数据。输入文件的第一行只有一个整数,表示数据的组数。保证
。
接下来行,每行包含一个仅由英文小写字母构成的字符串
,意义如题所述。
输出格式
输出行,每行包含一个整数,表示字符串
所有子串的所有拆分中,总共有多少个是优秀的拆分。
题目解析
同步赛考场上看到这题的部分分吓呆了。暴力95分这是什么意思?写发哈希,也不想去想正解了。
不过正解的思想还是不错的。
首先,我们发现只要找出所有形如的串即可。设有
个这样的串结束位置是
,有
个这样的串开始位置是
,则
我们考虑怎样快速求出和
。
我们枚举串中
的长度
。在原串上,我们每隔
设置一个关键点,可以发现,若
的长度为
,
必定恰好经过某两个相邻的关键点。于是我们可以枚举
经过的关键点。
考虑两个相邻的关键点,有
,我们求出
的最长公共前缀
和最长公共后缀
。若
,
串就一定存在,且可行的开始位置区间是
,可行的结束位置区间是
。由于每次是对一段区间加1,差分一波即可。
根据调和级数,枚举的时间复杂度
最长公共前后缀可用后缀数组实现。总时间复杂度。
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=60005; char s[maxn]; int a[maxn],b[maxn]; int bs[maxn]; int c[maxn],x[maxn],y[maxn]; struct SA { int sa[maxn],ht[maxn],rk[maxn]; int f[maxn][22]; int n; void run(char* s) { n=strlen(s+1); memset(x,0,sizeof(x)); int k,m=256; REP(i,1,m) c[i]=0; REP(i,1,n) c[x[i]=s[i]]++; REP(i,1,m) c[i]+=c[i-1]; PER(i,n,1) sa[c[x[i]]--]=i; for(k=1;k<=n;k<<=1) { int p=0; REP(i,n-k+1,n) y[++p]=i; REP(i,1,n) if(sa[i]>k) y[++p]=sa[i]-k; REP(i,1,m) c[i]=0; REP(i,1,n) c[x[i]]++; REP(i,1,m) c[i]+=c[i-1]; PER(i,n,1) sa[c[x[y[i]]]--]=y[i]; memcpy(y,x,sizeof(x)); x[sa[1]]=m=1; REP(i,2,n) { if(y[sa[i]]!=y[sa[i-1]] || y[sa[i]+k]!=y[sa[i-1]+k]) ++m; x[sa[i]]=m; } if(m>=n) break; } REP(i,1,n) rk[sa[i]]=i; k=0; REP(i,1,n) { if(k) k--; if(rk[i]==1) continue; int j=sa[rk[i]-1]; while(s[i+k]==s[j+k] && i+k<=n && j+k<=n) k++; ht[rk[i]]=k; } memset(f,0x3f,sizeof(f)); REP(i,2,n) f[i][0]=ht[i]; REP(j,1,20) REP(i,2,n) { if(i+(1<<(j-1))>n) break; f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } int LCP(int a,int b) { a=rk[a];b=rk[b]; if(a>b) swap(a,b);a++; int k=bs[b-a+1]; return min(f[a][k],f[b-(1<<k)+1][k]); } } sa,re; void solve() { scanf("%s",s+1); int n=strlen(s+1); sa.run(s); REP(i,1,n/2) swap(s[i],s[n-i+1]); re.run(s); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); REP(h,1,n) { for(int k=1;k<=n;k+=h) { if(k+h>n) break; int p=sa.LCP(k,k+h),q=re.LCP(n-k+1,n-k-h+1); p=min(p,h);q=min(q,h); if(p+q>h) { a[k+h+h-q]++;a[k+h+p]--; b[k-q+1]++;b[k+p-h+1]--; } } } LL res=0; REP(i,1,n) a[i]+=a[i-1],b[i]+=b[i-1]; REP(i,1,n-1) res+=1LL*a[i]*b[i+1]; printf("%lld\n",res); } int main() { REP(i,1,30000) { while((1<<(bs[i]+1))<i) bs[i]++; } int T; read(T); while(T--) solve(); return 0; } |