http://uoj.ac/problem/219 (题目链接)
题意
一个字符串求它有多少个形如AABB的子串。
Solution
其实跟后缀数组里面一个论文题poj3693处理方式差不多吧。
先处理出以位置${x}$为终点的${AA}$串的个数，区间加法用差分处理，然后处理出以位置${y}$为起点的${BB}$串的个数，统计答案。
细节
清空数组，后缀数组里面的${wa,wb}$数组也要清空。开LL
代码
// uoj219
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define inf 1ll<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
int sa[2][maxn],rank[2][maxn],height[2][maxn];
int ST[2][maxn][30],Log[maxn],bin[30];
char s[maxn];
LL cnt[maxn]; namespace Suffix {
int wa[maxn],ww[maxn],wb[maxn]; bool cmp(int *r,int a,int b,int l) {
return r[a]==r[b] && r[a+l]==r[b+l];
}
void da(char *r,int *sa,int n,int m) {
int i,j,p,*x=wa,*y=wb;
for (i=0;i<=n+1;i++) wa[i]=wb[i]=0; //important
for (i=0;i<=m;i++) ww[i]=0;
for (i=1;i<=n;i++) ww[x[i]=r[i]]++;
for (i=1;i<=m;i++) ww[i]+=ww[i-1];
for (i=n;i>=1;i--) sa[ww[x[i]]--]=i;
for (j=1,p=0;p<n;j<<=1,m=p) {
for (p=0,i=n-j+1;i<=n;i++) y[++p]=i;
for (i=1;i<=n;i++) if (sa[i]>j) y[++p]=sa[i]-j;
for (i=0;i<=m;i++) ww[i]=0;
for (i=1;i<=n;i++) ww[x[y[i]]]++;
for (i=1;i<=m;i++) ww[i]+=ww[i-1];
for (i=n;i>=1;i--) sa[ww[x[y[i]]]--]=y[i];
for (swap(x,y),x[sa[1]]=p=1,i=2;i<=n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p : ++p;
}
}
void calheight(int x,char *s,int *sa,int n) {
for (int i=1;i<=n;i++) rank[x][sa[i]]=i;
for (int k=0,i=1;i<=n;i++) {
if (k) k--;
int j=sa[rank[x][i]-1];
while (s[i+k]==s[j+k]) k++;
height[x][rank[x][i]]=k;
}
}
}
using namespace Suffix; int query(int k,int x,int y) {
if (x>y) swap(x,y);x++;
int l=Log[y-x+1];
return min(ST[k][x][l],ST[k][y-bin[l]+1][l]);
}
void Init() {
memset(s,0,sizeof(s));
memset(sa,0,sizeof(sa));
memset(ST,0,sizeof(ST));
memset(cnt,0,sizeof(cnt));
memset(rank,0,sizeof(rank));
memset(height,0,sizeof(height));
}
int main() {
bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
for (int i=2;i<maxn;i++) Log[i]=Log[i>>1]+1;
int T;scanf("%d",&T);
while (T--) {
Init();
scanf("%s",s+1);
int n=strlen(s+1);LL ans=0;
da(s,sa[0],n,300);
calheight(0,s,sa[0],n);
for (int i=1;i<=n>>1;i++) swap(s[i],s[n-i+1]);
da(s,sa[1],n,300);
calheight(1,s,sa[1],n);
for (int i=0;i<=1;i++)
for (int j=1;j<=n;j++) ST[i][j][0]=height[i][j];
for (int k=0;k<=1;k++)
for (int j=1;j<=20;j++)
for (int i=1;bin[j]+i<=n+1;i++)
ST[k][i][j]=min(ST[k][i][j-1],ST[k][i+bin[j-1]][j-1]);
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j+=i) { //计算以当前位置为终点AA有多少个
int nxt=min(query(0,rank[0][j-i],rank[0][j]),i);
int pre=min(query(1,rank[1][n-(j-i)+1],rank[1][n-j+1]),i);
if (nxt+pre>i) cnt[j-pre+i]++,cnt[j+nxt]--;
}
for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for (int i=1;i<=n;i++)
for (int j=1;j<=n-i;j+=i) { //计算以当前位置为起点BB有多少个
int nxt=min(query(0,rank[0][j],rank[0][j+i]),i);
int pre=min(query(1,rank[1][n-j+1],rank[1][n-(j+i)+1]),i);
if (nxt+pre>i) ans+=cnt[max(0,j+nxt-i-1)]-cnt[max(0,j-pre-1)];
}
printf("%lld\n",ans);
}
return 0;
}